백준 1697번 숨바꼭질 - 스위프트(Swift) 풀이

 현재 상황을 그래프로 치환할 수 있음을 떠올리면 그 뒤로 구현은 쉽다.

1. 각 점을 정점이라고 생각한다.
2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다.
3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다.

---

1. 각 점을 정점이라고 생각한다.

 현재 상황을 그래프로 나타낼 수 있다. 0부터 100,000번까지 총 100,001개의 정점이 있다.

 

2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다.

 X번 정점에서 1초 만에 다이렉트로 갈 수 있는 정점은 X+1, X-1, X*2이다. 그래프에 X에서 저 세 정점으로 가는 방향 간선을 추가해준다. 방향 간선이라는 것을 주의해야 한다. 10번 정점에서 20번 정점으로 갈 수는 있지만, 반대로 20번 정점에서 10번으로 가는 것은 불가능하다.

 

3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다.

 이제 N번 정점에서 K번 정점으로 가는 최단 거리를 구하면 된다. 간선 길이가 다 1이기 때문에 BFS로도 최단거리를 구할 수 있다. N번 정점에서 시작해서 K번 정점에 도착하기까지 몇 번의 depth를 거쳤는지 카운트해주면 된다.

 

---

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let N = input[0]
let K = input[1]

var queue = [(Int, Int)]()
var front = 0
var visit = Array(repeating: false, count: 100001)

queue.append((N, 0))    // N에서 시작
visit[N] = true

while true {    // BFS
    let x = queue[front].0
    let dist = queue[front].1
    
    front += 1  // pop
    
    if x == K {
        print(dist)
        break
    }
    
    let adjacents = [x * 2, x - 1, x + 1]   // 좌, 우, 2배 지점
    for adj in adjacents {
        if 0 <= adj && adj <= 100000 && !visit[adj] {
            visit[adj] = true
            queue.append((adj, dist + 1))
        }
    }
}