숨바꼭질3

HideAndSeek3.java

package backJoon_1697_HideAndSeek;
import java.util.*;

/*
 * 
 * 백준알고리즘
 * 1697. 숨바꼭질
 * https://www.acmicpc.net/problem/1697
 * 2021-03-28
 * 
 * */
public class Practice2 {
	static int N;
	static int K;
	static boolean[] check = new boolean[100001];
	static int numberOfSearching = 0;
	static List<answerCandidate> answerList = new ArrayList<>();
	
	public static class StepInfo{
		int nowN;
		int step;
		
		public StepInfo(int nowN, int step) {
			this.nowN = nowN;
			this.step = step;
		}
	}
	
	public static class answerCandidate{
		int step;
		
		public answerCandidate(int step) {
			this.step = step;
		}
	}
	
	
	public static void main(String[] args) {
		input();
		
		StepInfo stepInfo = new StepInfo(N, 0);
		
		Queue<StepInfo> q = new LinkedList<>();
		q.add(stepInfo);
		
		hideAndSeek(q);
		
		//걸음수 오름차순 정렬하여 최소걸음수 찾기
		Collections.sort(answerList, new Comparator<answerCandidate>(){
			@Override
			public int compare(answerCandidate o1, answerCandidate o2) {
				return Double.compare(o1.step, o2.step); //오름차순
			}
		});
		
		System.out.println(answerList.get(0).step);
	}

	private static void hideAndSeek(Queue<StepInfo> q) {
		
		while(!q.isEmpty()) {
			StepInfo stepInfo = q.poll();
			int n = stepInfo.nowN;
			
			check[n] = true;
			
			// 'nowN = K' 지만 step은 최소가 "아닌" 것이 "먼저" 도달할 수 있다.
			// 최소인 step을 언제 알수있지? '언제까지' 돌려야 하지? 무한정 돌릴순 없는거자나...
			if(n == K) {
				//System.out.println("n == K 일때 >> "+stepInfo.step);
				answerList.add(new answerCandidate(stepInfo.step));
			}
			
			// +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);
						//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);
						//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);
						q.add(nextStep);
						//check[tempN] = true;
					}
					
					break;
					
				}
			}
			
		}
		
	}

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

}