[BOJ] 13913 숨바꼭질 4

문제

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

풀이

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

public class Main {
	static int N,M;
	static Queue<Integer> queue;
	static int[] visit;
	static int[] parent;
	static void bfs(int st, int des) {
		parent[st] = st;
		visit[st] = 1;
		queue.add(st);
		
		while(!queue.isEmpty()) {
			int std = queue.poll();
			int next;
			if(std == des) {
				System.out.println(visit[std]-1);
				Stack<Integer> path = new Stack<Integer>();
				while(parent[std]!=std) {
					path.push(std);
					std = parent[std];
				}
				path.push(std);
				StringBuilder sb = new StringBuilder();
				while(!path.isEmpty()) {
					sb.append(path.pop()+" ");
				}
				System.out.println(sb);
				break;
			}
			next = std*2;
			if(next<=100000 && visit[next]==0) {
				visit[next] = visit[std]+1;
				parent[next] = std;
				queue.add(next);
			}
			next = std+1;
			if(next<=100000 && visit[next]==0) {
				visit[next] = visit[std]+1;
				parent[next] = std;
				queue.add(next);
			}
			next = std-1;
			if(next>=0 && visit[next]==0) {
				visit[next] = visit[std]+1;
				parent[next] = std;
				queue.add(next);
			}
		}
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	ArrayList<Integer> list = new ArrayList<Integer>();
    	ArrayList<Integer> left = new ArrayList<Integer>();
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	queue = new LinkedList<Integer>();
    	visit = new int[100001];
    	parent = new int[100001];
    	//계산
    	bfs(N,M);
	}
}