[Algorithm] 백준 - 13913번 숨바꼭질4 (Swift)

문제 소개

https://www.acmicpc.net/problem/13913

DFS를 하기에는 너무많은 경우의 수가 있으니 BFS로 풀어야 한다고 생각했다.
 

문제 풀이

숫자에 _를 붙여서 하면 더 가독성이 좋았다. visited를 활용하여 이전 값을 저장했다.

let nk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, k) = (nk[0], nk[1])

var visited = Array(repeating: -1, count: 100_001)
var queue = [(n, 0)]
var index = 0
visited[n] = 0

while queue.count > index {
    let current = queue[index].0
    let time = queue[index].1
    
    if current == k {
        print(time)
        break
    }
    
    for i in [-1, 1, current] {
        let next = current + i
        if 0...100_000 ~= next && visited[next] == -1 {
            visited[next] = current
            queue.append((next, time + 1))
        }
    }
    index += 1
}

var route: [Int] = []
var num = k

while num != n {
    route.append(num)
    num = visited[num]
}

route.append(n)
print(route.reversed().map { String($0) }.joined(separator: " "))