백준 13549 숨바꼭질3

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

이전 숨바꼭질 문제에서 순간이동에 걸리는 시간만 0초로 바뀐 문제이다.

이전 문제가 전형적인 bfs문제였기 때문에 당연히 bfs 풀이법으로 시작해보았다.

하지만 순간이동과 걷기의 비용이 다르기 때문에 일반적인 bfs로는 풀이가 어려웠다.

문제에서 요구하는 것이 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이므로, 탐색 시간을 기준으로 Priority Queue를 사용하여 bfs를 시도하였다.

초기 시도에서 일반적인 bfs가 아님을 잊어 평소대로 bfs 코드를 작성하였다 실패하였다.

아래는 실패한 초기 코드이다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, K) = readLine().split(' ').map{it.toInt()}

    val queue = PriorityQueue<Pos>{p1, p2 -> p1.time - p2.time}
    val visited = BooleanArray(100001){false}

    queue.offer(Pos(N,0))
    visited[N] = true

    while(queue.isNotEmpty()){
        val next = queue.poll()

        if(next.p == K){
            print(next.time)
            break
        }

        if(next.p * 2 < 100001 && !visited[next.p * 2]){
            visited[next.p * 2] = true
            queue.offer(Pos(next.p * 2, next.time))
        }
        if(next.p + 1 < 100001 && !visited[next.p + 1]){
            visited[next.p + 1] = true
            queue.offer(Pos(next.p + 1, next.time + 1))
        }
        if(next.p - 1 >= 0 && !visited[next.p - 1]){
            visited[next.p - 1] = true
            queue.offer(Pos(next.p - 1, next.time + 1))
        }
    }
}

data class Pos(val p: Int, val time: Int)

평소에, 일반적은 bfs코드를 작성할 때 메모리를 절약하기 위해 다음 위치를 queue에 넣기 전에 방문 체크를 시행하였다.

하지만 Priority Queue를 사용하는 bfs이기 때문에 방문 체크를 먼저 하고 큐에 넣는 방식은 문제가 발생한다.

(4, 12)를 예로 들어보자 - (위치, 시간)

시작 4로부터 (8, 0), (5, 1), (3, 1)의 탐색을 위한 Pos 객체가 발생하고, 다음 (8, 0)으로부터 (16, 0), (9, 1), (7, 1)이 발생한다.

(16, 0)은 범위 밖이라 일단 탐색에서 제외하면 PQ에는 시간 1인 Pos만 남는다.

문제는 여기서 발생한다.

특정 상황에서 (5, 1)과 (3, 1)의 경우를 생각해보자.

(3, 1)을 순간이동 두 번을 시행하면 (6, 1) - (12, 1) 로 1초만에 도착할 수 있다.

하지만 (5, 1)을 먼저 뽑고 (3, 1)을 뽑는 상황이 온다면, 그리고 위 실패 코드처럼 먼저 방문체크를 해버린다면?

(5, 1)에서 (6, 2)가 발생하고, 6번에 대한 방문체크를 시행해버리게 된다.

그러면 (3, 1)에서 (6, 1)이 발생해도 이미 방문체크가 되어있어 다시 큐에 들어가지 못하게 된다.

가중치가 달라서 Priority Queue를 사용해 BFS를 시행할 때는 미리 방문체크를 하지 않는 것이 좋겠다

이 점을 깨닫고 다시 작성한 코드이다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, K) = readLine().split(' ').map{it.toInt()}

    val queue = PriorityQueue<Pos>{p1, p2 -> p1.time - p2.time}
    val visited = BooleanArray(100001){false}

    queue.offer(Pos(N,0))
    visited[N] = true

    while(queue.isNotEmpty()){
        val next = queue.poll()
        visited[next.p] = true

        if(next.p == K){
            print(next.time)
            break
        }

        if(next.p * 2 < 100001 && !visited[next.p * 2]){
            queue.offer(Pos(next.p * 2, next.time))
        }
        if(next.p + 1 < 100001 && !visited[next.p + 1]){
            queue.offer(Pos(next.p + 1, next.time + 1))
        }
        if(next.p - 1 >= 0 && !visited[next.p - 1]){
            queue.offer(Pos(next.p - 1, next.time + 1))
        }
    }
}

data class Pos(val p: Int, val time: Int)

방문 체크를 다음 위치를 큐에서 뽑았을 때 함으로써 실패 예시 상황같은 미리 방문체크가 되어 정답 케이스가 손실되는 경우를 없앨 수 있다.