[17071] 숨바꼭질 5

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

17071번: 숨바꼭질 5

숨바꼭질 시리즈의 문제다. 선행 문제와 같은 방식으로 풀어보려 했으나 이번에는 동생이 움직인다는 조건이 붙어서 오답을 받았다. 풀이를 찾아보고 풀 수 있었던 문제였다. 

 

풀이

기존의 숨바꼭질 문제에서는 visited[n] 방문 배열을 "거리 n에 도달하는 데에 걸리는 시간"으로 설정하여 경로탐색으로 더 짧은 시간으로 갱신시켜 답을 구했다면 이번에는 동생이 이동한다는 조건 때문에 다른 방식으로 접근해야 한다. 수빈이가 동생이 도착할 장소에 미리 도착하여 한 칸 전진, 한 칸 후진 즉 2초를 소비하여 해당 자리에서 대기하는 것이 가능하다.

 

그렇다면 구분해야할것은 해당 시간과 위치에 홀수 초에 도착하는지 짝수 초에 도착하는지를 확인하여 해당 시간을 반환하면 된다. 따라서 방문 배열은 visited[t][k]:[[Bool]] 2차원 배열로 설정하고 t%2초에 k번째 위치에 방문했는지를 갱신하여 경로탐색을 해주면 된다. 시간이 갱신될 때마다 동생의 위치 k번째 배열 값이 참이라면 해당 시간을 반환하면 된다. 역시 설명보단 코드가 이해하기 더 쉬울 것이다.

 

정답 코드

import Foundation

let nk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nk[0]
var k = nk[1]
var ans = -1

var map = Array(repeating: Array(repeating: false, count: 2), count: 500001)
map[n][0] = true
var time = 0

func bfs(){
    var q = [n]
    var dq = [Int]()
    while !q.isEmpty{
        k += time
        dq = q.reversed()
        q.removeAll()
        if k<0 || k>500000{return}
        if map[k][time%2]{
            ans = time
            return
        }
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let next = [curr-1,curr+1,curr*2]
            
            for next in next{
                if next<0 || next>=500001{continue}
                if !map[next][(time+1)%2]{
                    map[next][(time+1)%2] = true
                    q.append(next)
                }
            }
        }
        time += 1
    }
}
bfs()
print(ans)