13913 - 숨바꼭질 4

문제

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

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

문제 설명

이전에 풀었던 숨바꼭질 문제에, 역추적이 포함된 문제이다.
가장 빠른 시간을 출력한 후, 해당 경우의 수에 어떻게 이동하는지 출력하는 문제인데, 이전 코드에 다음 분기로 넘어갈 때 마다 이전 좌표를 저장하는 부분만 추가해주면 되는 문제이다.

다만, 한 가지 신경써야될 부분은 "출발지와 도착지가 같을 경우"이다.
해당 경우에는 경로를 1번만 출력해야하는데, 일반적으로 코드를 짤 경우 경로가 두 번 출력될 수 있다.
이외에는 이전 문제와 똑같음.

package backjoon;
import java.io.*;
import java.util.*;

public class P_13913 {
    static int MAX = 200000;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void bfs(int N, boolean[] map, int[] time, int[] from) {
        Queue<Integer> q = new LinkedList<>();
        q.add(N);
        map[N] = true;
        while (!q.isEmpty()) {
            int current = q.poll();
            if (current + 1 < MAX) {
                if (!map[current + 1]) {
                    q.add(current + 1);
                    time[current + 1] = time[current] + 1;
                    from[current + 1] = current;
                    map[current + 1] = true;
                }
            }
            if (current - 1 >= 0) {
                if (!map[current - 1]) {
                    q.add(current - 1);
                    time[current - 1] = time[current] + 1;
                    from[current - 1] = current;
                    map[current - 1] = true;
                }
            }
            if (current * 2 < MAX) {
                if (!map[current * 2]) {
                    q.add(current * 2);
                    time[current * 2] = time[current] + 1;
                    from[current * 2] = current;
                    map[current * 2] = true;
                }
            }
        }
    }

    public static void print(int[] from, int N, int K) throws IOException{
        if (from[K] != N) print(from, N, from[K]);
        bw.write(from[K] + " ");
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = inputs[0];
        int K = inputs[1];
        int[] time = new int[MAX];
        int[] from = new int[MAX];
        boolean[] map = new boolean[MAX];
        bfs(N, map, time, from);
        bw.write(time[K] + "\n");
        if (N == K) { // 출발지와 도착지가 같을 경우 예외처리
            bw.write(Integer.toString(K));
        } else {
            print(from, N, K);
            bw.write(Integer.toString(K));
        }
        bw.flush();
    }
}