[백준 12851] 숨바꼭질 2 (Swift)

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

 

BFS & DP 

N에서 K까지 가는데 -1, +1, *2 경우로 이동할 수 있다. 이때 가장 빠르게 도달하는 시간과 그에 대한 경우의 수를 구하는 문제

 

접근방법

- BFS로 방문하고, 이미 방문했던 노드를 다시 큐에 넣지 않음

- 세가지 경우로 이동할 때, 다음 노드가 처음 방문하는 노드라면 다음 노드까지의 최단거리(dist[next])를 지금 노드까지의 최단거리+1을 입력해준다. 그리고 그 거리로 도달하는 경우의 수 (cnt[next])에는 지금 노드의 최단경로 경우의수 (cnt[now])를 넣어준다. {지금 노드로의 제일빨리 도달하는 경우들이 모두 다음 노드로까지 갈 수 있다는 것이기 때문에}

- 다음 노드가 처음 방문하는 노드가 아니고, 다음 노드까지의 최단거리와 지금노드까지의 최단거리+1이 같을 수 있다. 그때는 다음 노드까지 최단경로로 오는 경우의 수 + 지금노드까지 최단경로로 온 수를 더해주어야 한다.

 

오답노트

경우의 수는 현재 노드의 경우의 수를 늘 생각해줘야하는데 1 대입하고 이래서 몇번 틀렸다.

 

소스코드

import Foundation

func solution() {
    let input:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
    let n:Int = input[0]
    let k:Int = input[1]
    
    var dist:[Int] = [Int](repeating: Int.max, count: 100001)
    var cnt:[Int] = [Int](repeating: 0, count: 100001)
    
    dist[n] = 0
    cnt[n] = 1
    
    var q:[Int] = []
    q.append(n)
    
    while !q.isEmpty {
        let now = q.removeFirst()
        let nowdist = dist[now]
        
        if now-1 >= 0 && now-1 <= 100000 {
            if dist[now-1] > nowdist+1 {
                // 처음방문
                dist[now-1] = nowdist+1
                cnt[now-1] = cnt[now]
                q.append(now-1)
            } else if dist[now-1] == nowdist+1 {
                cnt[now-1] += cnt[now]
            } // 방문했는데 dist가 이미 내가 방문할 때보다 짧을때가 없다는 가정임 (bfs니까) - 원래 있던 dist값보다 작은 경우로 덮어써야 할 때가 오지 않음
        }
        if now+1 <= 100000 && now+1 >= 0 {
            if dist[now+1] > nowdist+1 {
                // 처음방문
                dist[now+1] = nowdist+1
                cnt[now+1] = cnt[now]
                q.append(now+1)
            } else if dist[now+1] == nowdist+1 {
                // 이전에 방문한적 있는데 또 최단거리로 방문한 경우
                cnt[now+1] += cnt[now]
            }
        }
        if now*2 <= 100000 && now*2 >= 0 {
            if dist[now*2] > nowdist+1 {
                // 처음방문
                dist[now*2] = nowdist+1
                cnt[now*2] = cnt[now]
                q.append(now*2)
            } else if dist[now*2] == nowdist+1 {
                cnt[now*2] += cnt[now]
            }
        }
    }
    
    print(dist[k])
    print(cnt[k])
}

solution()

 

 

참고 : https://eunsolsblog.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-12851%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-2