백준 13549 숨바꼭질 3 Java: 0-1 BFS로 0초 이동 처리

백준 13549 숨바꼭질 3 Java 풀이는 모든 이동의 비용이 같지 않다는 점에서 일반 BFS와 다르다. 처음 풀었을 때의 기록에는 두 번째 제출에서 통과했고 50분 timer가 6분 36초 남아 있었다고 적혀 있다. 첫 제출이 왜 틀렸는지는 남아 있지 않으므로 원인을 지어내기보다, 최종 풀이가 보장해야 할 순서를 0-1 BFS 기준으로 다시 정리했다.

이동을 weight가 있는 edge로 바꾼다

현재 위치가 x일 때 이동은 세 가지다.

다음 위치	걸리는 시간	edge weight
2 * x	0초	0
x - 1	1초	1
x + 1	1초	1

일반 BFS는 모든 edge weight가 같을 때 queue에 들어온 순서가 곧 최단 거리 순서가 된다. 여기서는 순간이동이 0초이므로 단순 FIFO queue만으로 그 성질을 설명하기 어렵다.

weight가 0 또는 1뿐인 graph에서는 deque를 사용한다.

• weight 0으로 이동: addFirst
• weight 1로 이동: addLast

비용이 늘지 않는 순간이동 후보를 앞쪽에서 먼저 처리하고, 1초가 필요한 이동은 뒤쪽에 둔다. relaxation으로 더 짧은 시간이 발견됐을 때만 deque에 넣는다.

Java 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    private static final int MAX_POSITION = 100_000;
    private static final int INF = Integer.MAX_VALUE;

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

        int start = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());

        System.out.println(zeroOneBfs(start, target));
    }

    private static int zeroOneBfs(int start, int target) {
        int[] distance = new int[MAX_POSITION + 1];
        Arrays.fill(distance, INF);

        Deque<Integer> deque = new ArrayDeque<>();
        distance[start] = 0;
        deque.addFirst(start);

        while (!deque.isEmpty()) {
            int current = deque.pollFirst();

            int teleported = current * 2;
            if (teleported <= MAX_POSITION
                    && distance[teleported] > distance[current]) {
                distance[teleported] = distance[current];
                deque.addFirst(teleported);
            }

            int left = current - 1;
            if (left >= 0
                    && distance[left] > distance[current] + 1) {
                distance[left] = distance[current] + 1;
                deque.addLast(left);
            }

            int right = current + 1;
            if (right <= MAX_POSITION
                    && distance[right] > distance[current] + 1) {
                distance[right] = distance[current] + 1;
                deque.addLast(right);
            }
        }

        return distance[target];
    }
}

예제로 확인하기

입력:

5 17

출력:

2

최소 시간 2초를 만드는 경로 중 하나는 다음과 같다.

5 -> 10 (0초)
10 -> 9 (1초)
9 -> 18 (0초)
18 -> 17 (1초)

start == target이면 답은 0이다. start > target인 경우에도 -1 이동을 반복하는 경로가 relaxation되어 올바른 시간이 나온다. 위치 범위를 0..100000으로 고정했으므로 -1, +1, *2를 넣기 전에 범위를 확인한다.

복잡도와 자료형

상태는 0..100000의 위치이고 각 위치에서 최대 3개의 edge만 확인한다.

• 시간 복잡도: O(MAX_POSITION)
• 공간 복잡도: distance와 deque에 O(MAX_POSITION)
• 자료형: 최단 시간은 위치 범위보다 작으므로 int로 충분하다.

일반 graph와 BFS의 기본은 그래프 자료구조와 DFS·BFS 차이, 임의의 양수 weight에서 priority queue를 사용하는 방식은 백준 1504 특정한 최단 경로에서 비교할 수 있다.

참고 자료

• 백준 13549: 숨바꼭질 3
• Internet Archive: 백준 13549 문제 스냅샷
• Oracle Java 21: ArrayDeque