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

 1697번 숨바꼭질 문제에 추가로 경우의 수까지 출력해야 하는 문제.

1. 각 점을 정점이라고 생각한다.
2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다.
3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다.
4. BFS를 돌 때 이미 방문했던 곳이더라도 해당 정점을 N에서 최단거리로 온 경우라면, 또 방문해서 경우의 수를 카운트해준다.

---

 ↓ 1, 2, 3번에 대한 설명은 1697번 풀이를 확인 ↓

 

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

 

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

 최단거리만 구하면 될 때는 단순하게 BFS를 돌다가 K번 정점을 만나면 끝내주면 된다. 그런데 경우의 수를 출력해줘야 하므로, 어떤 정점 X로 최단거리로 가는 방법이 여러가지라면 그 경우의 수를 모두 다 카운트해주어야 한다.

 예를 들어 1번에서 2번으로 최단 거리로 가는 방법은 다음과 같이 두 가지이다.

1. 1 + 1 = 2
2. 1 * 2 = 2

 포인트는 최단거리로 가는 경우의 수만 카운트 해주어야 한다는 것! 1 - 0 - 1 - 2 이렇게 최단거리가 아닌 경우는 카운트하면 안 된다.

 따라서 원래는 BFS를 돌 때 visit[i]를 확인해서 이미 방문한 곳이라면 방문을 안 했는데, 이제 방문한 곳이더라도 또 방문할 수 있다. 단, minDist[i]를 확인해서 최단거리로 온 경우에만 재방문해주어야 한다.

---

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 minDist = Array(repeating: 987654321, count: 100001)    // N에서 i번 정점까지 최단거리

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

var caseCount = 0

while true {    // BFS
    if front == queue.count { break }   // 큐가 비었으면 종료
    
    let x = queue[front].0
    let dist = queue[front].1
    
    if dist > minDist[K] { break }      // minDist[K]보다 멀리는 갈 필요 없음
    
    front += 1  // pop
    
    if x == K {
        minDist[K] = dist
        caseCount += 1
    }
    
    let adjacents = [x * 2, x - 1, x + 1]   // 좌, 우, 2배 지점
    for adj in adjacents {
        if 0 <= adj && adj <= 100000 && (dist + 1) <= minDist[adj] {  // minDist랑 같을 때도 경우의 수 카운트를 위해 삽입
            minDist[adj] = dist + 1
            queue.append((adj, dist + 1))
        }
    }
}

print(minDist[K])
print(caseCount)