[Algorithm] 백준 - 16928번 뱀과 사다리 게임 (Swift)

문제 소개

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)

 
이 문제에서는 이것보다는 더 효율적으로 짤순 없을듯...? 하다.