백준 12851번. 숨바꼭질 2 (Java)

Problem

• 문제 링크

수빈이는 동생이랑 숨바꼭질을 하고 있습니다.

수빈이는 N 에서 시작하고 동생은 K 에 있습니다.

수빈이는 1초에 +1, -1, *2 위치로 순간이동이 가능합니다.

수빈이가 동생을 찾는 가장 빠른 시간과 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 문제입니다.

Solution

백준 1697번 숨바꼭질 문제의 진화형입니다.

최단 시간을 구하라는 점은 똑같지만, 이번에는 최단 시간에 만나는 모든 경우를 구해야 합니다.

그래서 푸는 방법이 조금 다릅니다.

1. BFS 를 종료 기준을 시간으로 탐색

BFS에는 시간이 0 부터 차례대로 쌓입니다.

만약 수빈이가 동생을 2 초에 만났고, BFS 탐색이 3 초를 넘어가면 이미 최단 시간이 아니기 때문에 그 이후는 더 볼 필요가 없습니다.

2. 중복 방문의 허용

수빈이가 최단 시간에 동생을 만나는 방법은 여러 가지가 있을 수 있습니다.

예를 들어 입력으로 1 4 가 주어졌다고 합니다.

그러면 수빈이가 동생을 만나는 최단 루트는 *2, *2 로 1 2 4 입니다.

하지만 +1, *2 로 움직이면 똑같이 1 2 4 루트로 동생을 만날 수 있습니다.

만약 위치 2에서의 중복 방문을 허용하지 않는다면 확인 할 수 없습니다.

3. 그러나 모든 중복을 허용하지 않기

똑같은 위치에 다시 방문했을 때 세가지 경우를 생각해봐야 합니다.

3.1. 이전 방문 시간과 현재 방문 시간이 일치할 때

time[next] == time[now] + 1 인 경우입니다.

동일한 시간에 도착했다면 최종 목적지에 도달하는 시간도 동일할 가능성이 있기 때문에 Queue 에 넣어줍니다.

3.2. 이전 방문 시간이 현재 방문 시간보다 빠른 경우

time[next] < time[now] + 1 인 경우입니다.

현재 방문 시간이 더 느리기 때문에 목적지에 최단 시간으로 도달할 가능성이 없습니다.

제외해줍니다.

3.3. 이전 방문 시간이 현재 방문 시간보다 늦은 경우

time[next] > time[now] + 1 인 경우입니다.

현재 시간이 더 빠르기 때문에 Queue 에 넣어줍니다.

그러나 사실 발생하지 않는 케이스입니다.

BFS 는 시간 순서로 진행되고 있습니다.

1 초에 도달하는 곳을 모두 확인하고 2 초에 도달할 수 있는 곳을 모두 확인하고.. 3초에..

따라서 이전에 방문한 곳이 현재 시간보다 클 가능성은 없습니다.

실제 로직에 영향을 주진 않으므로 Queue 에 넣는 조건으로 사용해도 괜찮습니다.

방금 예시로 든 1 2 4 를 다시 생각해봅니다.

두 경우 다 1초에 2로 이동하기 때문에 중복 방문을 해도 괜찮습니다.

하지만 만약 2에 방문하는 시간이 2초, 3초로 다를 경우, 더 늦은 3초는 볼 필요가 없기 때문에 방문을 허용하지 않습니다.

Java Code

import java.util.*;
import java.io.*;

class Main {
    static int N, K;
    static int[] time = new int[100001];
    static int minTime = 987654321;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) {
            System.out.println((N-K) + "\n1");
            return;
        }

        bfs();

        System.out.println(minTime + "\n" + count);
    }

    static void bfs() {
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(N);
        time[N] = 1;

        while (!q.isEmpty()) {
            int now = q.poll();

            // now 방문 시간이 최소 시간보다 크면 뒤는 더 볼 필요 없음
            if (minTime < time[now]) return;

            for (int i=0; i<3; i++) {
                int next;

                if (i == 0)         next = now + 1;
                else if (i == 1)    next = now - 1;
                else                next = now * 2;

                if (next < 0 || next > 100000) continue;

                if (next == K) {
                    minTime = time[now];
                    count++;
                }

                // 첫 방문이거나 (time[next] == 0)
                // 이미 방문한 곳이어도 같은 시간에 방문했다면 (time[next] == time[now] + 1)
                // 경우의 수에 추가될 수 있기 때문에 Queue 에 한번 더 넣어줌
                if (time[next] == 0 || time[next] == time[now] + 1) {
                    q.add(next);
                    time[next] = time[now] + 1;
                }
            }
        }
    }
}