[백준/Java] 13549 숨바꼭질 3

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

1. 문제 요약

술래가 동생과 숨바꼭질을 한다.
술래는 현재 점 N에 있고, 동생은 점 K에 있다.
술래는 걷거나 순간이동을 할 수 있다.
점 X에서 걷는다면 1초 후에 X-1 또는 X+1로 이동한다. 순간이동을 한다면 0초 후에 2*X로 이동한다.
술래가 동생을 잡을 수 있는 가장 빠른 시간을 구하여라.

이때 N과 K는 0 이상 10만 이하의 값을 갖는다.

2. 문제 접근

입력이 가질 수 있는 값이 최대 10만이므로 시간복잡도는 $O(NlogN)$까지 가능하다.
술래가 이동할 수 있는 경우를 일종의 그래프로 생각한다면 우선순위 큐와 BFS를 활용해 문제를 해결할 수 있다.
이 우선순위 큐는 흐른 시간이 가장 짧은 것부터 꺼내도록 하여, BFS를 수행하다가 동생의 위치에 처음 도달한다면 그 때의 값이 정답이다.

3. 풀이

기본적인 아이디어는 다음과 같다.

1. {위치, 걸린 시간}을 입력받아 걸린 시간이 최소인 것부터 얻어지는 PriorityQueue 선언
2. BFS에서 방문 여부를 기록하는 visited 배열 선언
3. 목표점 K에 도달할 때까지 BFS를 수행한다.
   3.1. 우선순위 큐에서 값을 꺼내 방문했던 곳이라면 넘어간다.
   3.2. 방문 여부를 기록하고 순간이동, 좌우 이동을 새로 우선순위 큐에 넣는다.

계속 걸린 시간이 최소인 것부터 꺼내기 때문에 K에 처음 도달한 경우를 도달할 수 있는 가장 빠른 시간이라고 할 수 있다.

이를 구현한 코드는 다음과 같다.

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

public class Main {
    
    public static final int MAX_POS = 100000;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 술래의 최초 위치(시작점)
        int K = Integer.parseInt(st.nextToken()); // 동생의 최초 위치(목표점)

        // {위치, 걸린 시간}을 입력받아 걸린 시간이 짧은 것부터 출력하는 우선순위 큐
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] a1, int[] a2) {
                return Integer.compare(a1[1], a2[1]);
            }
        });
        
        // 방문 여부 배열 선언 및 초기화
        boolean[] visited = new boolean[MAX_POS+1]; // 0부터 MAX_POS까지 가능하므로 1을 더해 선언
        for (int i = 0; i < MAX_POS+1; i++) {
            visited[i] = false;
        }

        // 시작점을 선언하고 우선순위 큐에 넣기
        int[] start = {N, 0}; // {위치, 걸린 시간}
        pq.add(start);
        
        int leastTime = Integer.MAX_VALUE; // 정답이 될 가장 빠른 시간

        // 목표점 K에 도달할 때까지 BFS 수행
        while (!pq.isEmpty()) {
            int[] now = pq.poll();

            // 만약 방문했던 곳이라면 넘어간다.
            if (visited[now[0]]) continue;

            // 방문 여부 기록
            visited[now[0]] = true;

            // 만약 현재 위치가 K라면 정답을 얻은 것이므로 루프를 끝낸다.
            if (now[0] == K) {
                leastTime = now[1];
                break;
            }

            // 순간이동하는 경우를 우선순위 큐에 넣기
            int[] teleport = {2*now[0], now[1]}; // 위치는 2*X, 시간은 0초를 더함
            // 범위를 넘어가지 않는 경우, 방문하지 않은 경우에만 우선순위 큐에 넣는다.
            if (teleport[0] <= MAX_POS && !visited[teleport[0]]) {
                pq.add(teleport);
            }

            // 왼쪽으로 걷는 경우 넣기
            int[] walkLeft = {now[0]-1, now[1]+1}; // 위치는 X-1, 시간은 1초를 더함
            // 범위를 넘어가지 않는 경우, 방문하지 않은 경우에만 넣음
            if (walkLeft[0] >= 0 && !visited[walkLeft[0]]) {
                pq.add(walkLeft);
            }

            // 오른쪽으로 걷는 경우 넣기
            int[] walkRight = {now[0]+1, now[1]+1}; // 위치는 X+1, 시간은 1초를 더함
            // 범위를 넘어가지 않는 경우, 방문하지 않은 경우에만 넣음
            if (walkRight[0] <= MAX_POS && !visited[walkRight[0]]) {
                pq.add(walkRight);
            }
        }

        // 정답 출력
        // K에 도달하지 못하는 경우는 없으므로 그냥 값을 갱신하고 끝낸 뒤 출력해도 된다.
        System.out.println(leastTime);
    }
}

4. 회고

BFS와 같은 탐색을 할 때는 항상 방문 여부를 언제 기록해야 하는지 고민이 된다.
우선순위 큐에 값을 넣으면서 방문 여부를 기록하면 시간복잡도를 더 낮출 수 있으며, 이 문제에서도 순간이동을 먼저 넣도록 하면 이러한 방식이 가능할 것이다.
다만 모든 문제에서 가능하지는 않은 것으로 기억하고, 그 차이가 그렇게 의미가 있는 것 같지는 않기 때문에 일반적인 방식으로 풀이를 하였다.