[백준] 13913번 - 숨바꼭질 4 (Gold 4)

문제 링크

백준 13913번 - 숨바꼭질 4 (Gold 4)

문제 설명

현재 점 N(0 $\leq$ N $\leq$ 100,000)에서 점 K(0 $\leq$ K $\leq$ 100,000)까지 이동하려고 한다.
점 X에서 이동할 수 있는 방법은 다음의 세 가지이며, 세 방법 모두 한 번에 1초가 소요된다.

1. X - 1까지 걸어가기
2. X + 1까지 걸어가기
3. 2 * X의 위치로 순간이동하기

점 N에서 점 K까지 이동하는데 드는 최소의 시간과 최단 경로를 출력하시오.
최단 경로가 여러가지가 가능하다면, 그 중 아무거나 한 개만 출력하면 된다.

정답 코드 및 설명

최소 시간을 구하는 것은 BFS를 통해 가능하다.
이 문제에서 중요한 것은 역추적을 통한 최단 경로 찾기이다.
이는 BFS를 수행할 때 각 지점까지 걸리는 최소 시간만을 저장하지 않고, 직전의 위치까지 저장함으로써 가능하다.

BFS의 수행 과정은 코드의 21행 ~ 35행, 역추적 과정은 코드의 40행 ~ 52행을 참조하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ13913 {
    final int MAX = 200000;
    int n, k;
    int[][] bfs = new int[MAX + 1][2];

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
    }

    void bfs() {
        Queue<Integer> position = new LinkedList<>();
        position.add(n);
        bfs[n][0] = 1;
        bfs[n][1] = n;
        while (!position.isEmpty()) {
            int curr = position.poll();
            if (curr == k) break;
            int[] next = {curr - 1, curr + 1, 2 * curr};
            for (int i : next) {
                if (i < 0 || i > MAX) continue;
                if (bfs[i][0] != 0) continue;
                bfs[i][0] = bfs[curr][0] + 1;
                bfs[i][1] = curr;
                position.add(i);
            }
        }
    }

    void traceback() {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> traceback = new Stack<>();
        int curr = k;
        traceback.push(curr);
        while (curr != n) {
            curr = bfs[curr][1];
            traceback.push(curr);
        }
        while (!traceback.isEmpty()) {
            sb.append(traceback.pop()).append(' ');
        }
        System.out.println(sb);
    }

    void solution() throws IOException {
        input();
        bfs();
        System.out.println(bfs[k][0] - 1);
        traceback();
    }

    public static void main(String[] args) throws IOException {
        new BOJ13913().solution();
    }
}