백준 12851번: 숨바꼭질 2

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

문제 풀이

BFS

dist[i] = N에서 i로 이동하는 최단 거리

count[i] = N에서 i로 최단 거리로 이동하는 방법의 수

N에서부터 이동 및 순간이동을 할 때 그 좌표로 가는 것이 dist에 저장된 최단 거리보다 짧을 때만 이동 및 탐색을 해서 최단 거리일 때만 방법의 수를 최신화해 최단 거리로 이동하는 방법의 수를 구함

이 때 다음 좌표로 이동하는 거리 d + 1이 dist에 저장된 값보다 작다면 좌표에서 다음 좌표로 가는 것이 최단 거리이고 N에서부터 현재 좌표로 최단 거리로 이동하는 방법의 수가 count[x]이므로 count[nx]에 count[x]를 대입해 N에서부터 nx까지 가는 최단 거리로 이동하는 방법의 수를 나타냄

만약 d + 1이 dist에 저장된 값과 같다면 최단 거리로 가는 다른 방법의 수를 찾은 것이므로 count[nx]에 count[x]를 더해주어 최단 거리로 이동하는 방법의 수를 저장함

이렇게 탐색을 하다보면 이전에 이동했던 것보다 현재 좌표로 가는 더 빠른 거리를 찾을 수도 있으므로 큐에서 좌표와 거리를 꺼냈을 때 dist에 저장된 값을 비교해 최단 거리일 때만 탐색을 하도록 함

이러면 dist[K]에 N에서 K로 가는 최단 거리가 저장되고 count[K]에 N에서 K로 최단 거리로 이동하는 방법의 수가 저장되므로 출력하면 정답

풀이 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

현재 이동과 순간이동이 둘다 1초가 걸린다고 했고 가장 빠른 시간에 도착하는 시간과 그 시간으로 이동하는 방법이 몇가지 구하는 것은 이동과 순간이동이 거리가 1인 것으로 생각하면 최단 거리와 최단 거리로 이동하는 방법의 가짓수를 구하는 문제가 된다.

따라서 N에서부터 BFS를 이용하면서 K로 가는 최단 거리와 최단 거리로 이동하는 방법의 가짓수를 구하면 된다. 이 때 특정 좌표로 이동했을 때 그 좌표로 이동할 수 있는 최단 거리보다 거리가 크다면 그 좌표로 이동하는 더 빠른 방법이 있으므로 우리가 구하는 최단 거리를 구하는 방법과는 거리가 멀기 때문에 탐색을 그만해야 한다.

이에 따라 N에서 특정 좌표까지 가는 최단 거리를 저장하는 배열 dist, N에서 특정 좌표까지 최단 거리로 이동하는 방법의 수를 저장하는 배열 count를 정의하고 BFS를 이용하기 위해 현재 좌표와 거리를 저장할 수 있는 큐 queue를 정의힌다.

그 이후에 N에서부터 이동하기 위해 큐에 좌표 N과 거리 0을 넣는다. 그 이후에 큐에서 현재 좌표 x, 거리 d를 하나씩 꺼내면서 현재 거리가 최단 거리가 맞는지 확인하기 위해 dist[x]와 d를 비교해 d가 더 크다면 최단 거리가 아닌 것이므로 넘어간다.

그런 경우가 아니라면 이동과 순간이동을 했을 때 그 좌표로 이동하는 것이 최단 거리인지를 비교하기 위해 다음 좌표 nx, nx로 이동하는 거리 d + 1이 있을 때 nx가 좌표 범위를 벗어나지 않는다면 dist[nx]와 d + 1를 비교해 dist[nx]가 더 크다면 이전에 nx로 이동하는 방법보다 현재 x에서 nx로 이동하는 방법이 더 적은 거리로 이동하는 방법이므로 dist[nx]에 d + 1을 대입하고 count[nx]에 x로 최단 거리로 이동하는 방법인 count[x]를 대입하고 큐에 nx, d + 1을 넣는다.

만약 d + 1이 dist[nx]와 같다면 nx로 최단 거리로 이동하는 새로운 방법을 찾은 것이므로 count[nx]에 x에 최단 거리로 이동하는 방법의 수 count[x]를 더해주고 nx로 최단 거리로 이동하는 거리가 이미 큐에 들어가 있을 것이므로 큐에 더 넣지는 않는다.

이런 단계들을 큐가 빌때까지 반복하면 dist[K]에 N에서 K로 가는 최단 거리, count[K]에 최단 거리로 이동하는 방법의 수가 저장되어 있으므로 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val K = nextInt()
    val queue = ArrayDeque<IntArray>()
    if(N != K){
        queue.add(intArrayOf(N, 0))
    }
    val dist = IntArray(100001){Int.MAX_VALUE}
    dist[N] = 0
    val count = IntArray(100001)
    count[N] = 1
    while(queue.isNotEmpty()){
        val(x, d) = queue.removeFirst()
        if(d > dist[x]) continue
        for(nx in intArrayOf(x - 1, x + 1, x * 2)){
            if(nx < 0 || nx > 100000) continue
            if(d + 1 < dist[nx]){
                dist[nx] = d + 1
                count[nx] = count[x]
                queue.add(intArrayOf(nx, d + 1))
            } else if(d + 1 == dist[nx]){
                count[nx] += count[x]
            }
        }
    }
    println(dist[K])
    println(count[K])
}