백준 - 숨바꼭질 4 - 13913 - swift

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

13913번: 숨바꼭질 4

 

 

 

 

문제는 너비 우선 탐색 - bfs 유형이다. 

 

X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

총 3가지의 움직임이 있는데, 3가지 모두 다 1초 후에 발생한다. 

 

문제는 가장 빠르게 동생을 찾을 수 있는 시간을 묻고 있다.

모두 1초이므로, 간단하게 bfs를 통해서 풀 수 있다. 

 

문제는 가장 빠른 시간에 도착한 경로를 같이 출력해야 한다. 

 

아주 간단하게 생각하면, bfs로 하는데, 큐에 지금까지 방문한 경로들을 모두 넣어주는 것이다.

하지만 최대 탐색범위가 10만이므로, 이는 메모리 초과로 이어질 수 있다. ( 실제로 그렇게 푸니,  메모리 초과가 발생했다. ) 

( 대체로, 큐에 탐색할 때마다 큐의 원소들이 증가하는 경우에는 메모리 초과로 이어지는 경우가 많다. ) 

 

그럼 어떻게 효과적으로 찾을 수 있을까? 

 

사실 1초 후에 힌트가 있다. 

모두 1초 후이므로, bfs에서 탐색 조건도 먼저 방문하면 그게 가장 최적 시간이다.

 

그러므로, 방문 체크하는 배열을 Bool 타입이 아닌, Int 타입으로, dp [ x ] = x위치에 도착했을 때, 이전 위치 값 

으로 저장한다. 

 

그렇게 하면 이제 큐에는 더 이상 원소가 배열일 필요가 없고, 하나의 Int 타입만 넣어서 빠르게 탐색할 수 있다. 

 

그럼 찾은 경로는? 

dp를 거꾸로 탐색하면 된다. 

즉, 동생의 위치 K에서 시작하여,   dp [K] 

처음의 수빈이의 위치로 도달할 때까지 while문을 돌면 된다.

let inp = readLine()!.split(separator: " " ).map{Int(String($0))!}
let N = inp[0], K = inp[1]
let MX = 100000
var dp = Array(repeating: -1, count: MX+1)
dp[N] = 0
var queue = [N]
var q = 0
while queue.count > q {
    let f = queue[q]
    q += 1
    
    if f == K {
        var ans = [K]
        var k = K
        while k != N {
            ans.append(dp[k])
            k = dp[k]
        }
        var str = ""
        ans.reversed().forEach {
            str += String($0) + " "
        }
        str.removeLast()
        print(ans.count-1)
        print(str)
        break
    }
    
    let list = [f+1, f-1, f*2]
    list.forEach {
        if (0...MX).contains($0), dp[$0] == -1 {
            dp[$0] = f
            queue.append($0)
        }
    }
}