BOJ 13913 숨바꼭질 4

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

public class Main {
    static int INF=100001;
    static int N, K;
    static int[] locations, time;
    public static void main(String[] args) 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());

        if(N==K){
            System.out.println(0);
            System.out.println(K);
        }else{
            locations = new int[INF]; // 이동 위치 저장 목적
            time = new int[INF]; // 걸리는 시간 저장 목적.

            Arrays.fill(time, -1); // -1이면 방문 안함.
            bfs(N);
            System.out.println(time[K]);
            printRes();
        }
    }

    static void bfs(int startLocation){
        time[startLocation] = 0;

        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(startLocation);

        while(!queue.isEmpty()){
            Integer curr = queue.poll();

            for(int next: new int[]{curr+1, curr-1, curr*2}){
                if (next < 0 || next >= INF) continue;

                if(time[next]==-1){
                    time[next] = time[curr]+1;
                    locations[next] = curr;
                    queue.offer(next);
                }
            }
        }
    }

    static void printRes(){

        int index = K;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.add(K);
        while( index != N){
            stack.push(locations[index]);
            index = locations[index];
        }

        StringBuilder sb = new StringBuilder();

        while(!stack.isEmpty()){
            sb.append(stack.pop()).append(" ");
        }
        System.out.println(sb);
    }
}