백준 알고리즘_13913_숨바꼭질4

HideAndSeek4.java

package backJoon_1697_HideAndSeek;
import java.util.*;

/*
 * 
 * 백준알고리즘
 * 1697. 숨바꼭질
 * https://www.acmicpc.net/problem/13913
 * 2021-04-03
 * 
 * */
public class Practice2 {
	static int N;
	static int K;
	static boolean[] check = new boolean[100001];
	static int numberOfSearching = 0;
	static int[] route = new int[100001];
	
	public static class StepInfo{
		int nowN;
		int step;
		
		public StepInfo(int nowN, int step) {
			this.nowN = nowN;
			this.step = step;
		}
	}
	
	public static void main(String[] args) {
		input();
		
		List<Integer> records = new ArrayList<>();
		records.add(N);
		StepInfo stepInfo = new StepInfo(N, 0);
		
		Queue<StepInfo> q = new LinkedList<>();
		q.add(stepInfo);
		
		hideAndSeek(q);
	}

	private static void hideAndSeek(Queue<StepInfo> q) {
		
		while(!q.isEmpty()) {
			StepInfo stepInfo = q.poll();
			int n = stepInfo.nowN;
			
			//check[n] = true;
			
			if(n == K) {
				if(N == K) {
					System.out.println(stepInfo.step);
					
					System.out.println(N);
					return;
				}
				System.out.println(stepInfo.step);
				
				Stack<Integer> stack = new Stack<>();
				stack.push(route[K]);
				int idx = route[K];
				
				for(int i = 0; i < stepInfo.step - 1; i++){
					stack.push(route[idx]);
					idx = route[idx];
				}
				
				while(!stack.isEmpty()) {
					System.out.print(stack.pop()+" ");
				}
				System.out.print(K);
			}
			
			// +1, -1, *2 셋 중 어느 연산을 할 건지 탐색
			StepInfo nextStep;
			int tempN;
			for(int d = 0; d < 3; d++) {
				switch(d) {
				case 0:
					tempN = n;
					tempN += 1;
					if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
						nextStep = new StepInfo(tempN, stepInfo.step + 1);
						q.add(nextStep);
						route[tempN] = n;
						check[tempN] = true;
					}
					
					break;
					
				case 1: 
					tempN = n;
					tempN -= 1;
					if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
						nextStep = new StepInfo(tempN, stepInfo.step + 1);
						q.add(nextStep);
						route[tempN] = n;
						check[tempN] = true;
					}
					
					break;
					
				case 2:
					tempN = n;
					tempN *= 2;
					if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
						nextStep = new StepInfo(tempN, stepInfo.step + 1);
						q.add(nextStep);
						route[tempN] = n;
						check[tempN] = true;
					}
					
					break;
					
				}
			}
			
		}
		
	}

	private static void input() {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		K = sc.nextInt();
	}

}