→ Problems
[Algorithm] 백준 - 16928번 뱀과 사다리 게임 (Swift)
Swift librarian
2024. 6. 7. 13:57
문제 소개
https://www.acmicpc.net/problem/16928
뱀과 사다리 게임을 하는데 주사위를 굴려야 하는 횟수의 최솟값을 구하는 문제이다.

문제 풀이
DFS 를 활용한 풀이
board, visited 를 통해 보드의 정보, 방문여부를 저장하여 구현했다. 처음에 틀렸는데 이유는 뱀을 타고 내려가는 경우는 일부로 고려하지 않았는데, 뱀을 타고 내려가는 경우에도 빨리 도착하는 경우가 있다.
import Foundation
let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var board = Array(repeating: 0, count: 101)
var visited = Array(repeating: false, count: 101)
for _ in 0..<n {
let xy = readLine()!.split(separator: " ").map { Int($0)! }
let (x, y) = (xy[0], xy[1])
board[x] = y
}
for _ in 0..<m {
let uv = readLine()!.split(separator: " ").map { Int($0)! }
let (u, v) = (uv[0], uv[1])
board[u] = v
}
let dice = [1, 2, 3, 4, 5, 6]
var queue = [(1, 0)]
var idx = 0
var answer = 0
while queue.count > idx {
let poped = queue[idx]
idx += 1
if poped.0 >= 100 {
answer = poped.1
break
}
for num in dice {
let next = poped.0 + num
if next > 100 { continue }
if !visited[next] {
visited[next] = true
queue.append((board[next] == 0 ? next : board[next], poped.1 + 1))
}
}
}
print(answer)
이 문제에서는 이것보다는 더 효율적으로 짤순 없을듯...? 하다.
