[BOJ 백준] 13913 - 숨바꼭질 4, Java(자바)

문제

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

13913번: 숨바꼭질 4

풀이

bfs를 이용해 1 더하거나 1 빼거나 2를 곱한 값들을 큐에 넣으면서 부모 배열을 업데이트 시켜준다. 만약 다음 값이 K라면 while문을 빠져나온 후 부모를 따라가면서 스택에 넣었다가 하나하나 빼면서 출력한다.

코드

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

public class Main
{
    static int[] parents;
    static Queue<Integer> queue;
    
    public static void main(String[] args) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        if (N == K) {
            System.out.println(0 + "\n" + K);
            return;
        }
        
        parents = new int[100001];
        Arrays.fill(parents, -1);
        StringBuffer sb = new StringBuffer();
        queue = new LinkedList<Integer>();
        queue.offer(N);
        
        while(!queue.isEmpty()) {
            int temp = queue.poll();
            int add = temp + 1;
            int sub = temp - 1;
            int mul = temp * 2;
            
            if (add == K || sub == K || mul == K) {
                parents[K] = temp;
                break;
            }
            
            if (add <= 100000 && parents[add] == -1)
                move(add, temp);
            if (sub >= 0 && parents[sub] == -1)
                move(sub, temp);
            if (mul <= 100000 && parents[mul] == -1)
                move(mul, temp);
        }
        
        int cur = K;
        Stack<Integer> stack = new Stack<Integer>();
        while (cur != N) {
            stack.push(cur);
            cur = parents[cur];
        }
        sb.append(stack.size() + "\n" + N + " ");
        while (!stack.empty())
            sb.append(stack.pop() + " ");
        System.out.println(sb);
    }
    
    public static void move(int val, int parent) {
        parents[val] = parent;
        queue.offer(val);
    }
}