[백준] 13913번 숨바꼭질 4

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

13913번: 숨바꼭질 4

parent 배열에 직전 번호를 기록하여 이동 경로 저장

 

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

public class Main {

    static int N;
    static int K;
    static boolean[] visit = new boolean[100001];
    static int[] arr = new int[100001];
    static int[] parent = new int[100001];
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        Arrays.fill(parent, -1);
        if (N == K) {
        	System.out.print(0);
        } else {
       		bfs();
        }

        sb.append(arr[K]).append("\n");

        Stack<Integer> stack = new Stack<>();
        stack.push(K);
        while(parent[K] != -1) {
        	stack.push(parent[K]);
        	K = parent[K];
        }
        while(!stack.isEmpty()) {
        	sb.append(stack.pop() + " ");
        }
        System.out.println(sb);

    }

    public static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        visit[N] = true;
        while (!q.isEmpty()) {
            int num = q.poll();

            for (int i = 0; i < 3; i++) {
                int next = 0;
                if (i == 0) {
                	next = num - 1;
                } else if (i == 1) {
                	next = num + 1;
                } else {
                	next = num * 2;
                }

                if (next >= 0 && next < arr.length && !visit[next]) {
                    q.offer(next);
                    arr[next] = arr[num] + 1;
                    parent[next] = num;
                    visit[next] = true;
                }
            }

        }
    }

}