숨바꼭질 2

다른사람 코드

import Foundation
//12851 숨바꼭질

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

var sec = Array(repeating: -1, count: len+1)
var cnt = Array(repeating: 0, count: len+1)

func bfs(_ x: Int) {
    var queue = [x]
    var index = 0
    sec[x] = 0
    cnt[x] = 1
    
    while index < queue.count {
        let node = queue[index]
        index += 1
        
        for nx in [node+1, node-1, node*2] {
            if (0...len).contains(nx){
                if sec[nx] == -1 {
                    sec[nx] = sec[node]+1
                    cnt[nx] = cnt[node]
                    queue.append(nx)
                }else if sec[node]+1 == sec[nx] {
                    cnt[nx] += cnt[node]
                }
            }
        }
    }
}

bfs(n)
print(sec[k])
print(cnt[k])

---

해석

for nx in [node+1, node-1, node*2] {
            if (0...len).contains(nx){
                if sec[nx] == -1 {
                    sec[nx] = sec[node]+1
                    cnt[nx] = cnt[node]
                    queue.append(nx)
                }else if sec[node]+1 == sec[nx] {
                    cnt[nx] += cnt[node]
                }
            }
        }

이부분에서 감탄을 좀 했는데

if (0...len).contains(nx){

여기서 이미 nx의 범위를 지정해줌

if sec[nx] == -1 {
                    sec[nx] = sec[node]+1
                    cnt[nx] = cnt[node]
                    queue.append(nx)

방문하지 않은 곳이라면 sec[nx]는 sec[node]+1 >> 1 뒤에 도착하는 거니까

cnt[nx] = cnt[node]인 이유는 현재 방문하지 않은곳인데 지금 node에서 가는 방법이 있으니 cnt를 같게 해줌

 

else if sec[node]+1 == sec[nx] {
                    cnt[nx] += cnt[node]
                    }

방문한곳인데, sec[node]+1 == sec[nx]이라면 결국 현재 노드에서도 갈 수 있는 곳이니, cnt를 더해준다. 

이유는 원래 cnt[nx]는 전에 저장했던 cnt이고, 현재 노드cnt를 이용해서 또 갈 수 있으니까