[백준 1697번] 숨바꼭질 / Java

[boj 1697번] 숨바꼭질

 

N : 수빈이의 위치

K : 동생의 위치

X+1 or X-1 : 걷기

X*2 : 순간이동

 

동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제

 

 

public class Main {
	static int N, K;
	static int check[] = new int[100001];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		bfs();
		
	}
	
	public static void bfs() {
		Queue q = new LinkedList();
		
		q.add(N);
		check[N] = 1;
		
		while(!q.isEmpty()) {
			N = q.poll();
			
			if(N == K)
				break;
			
			if(N+1 <=100000 && check[N+1] == 0) {
				q.add(N+1);
				check[N+1] = check[N]+1;
			}
			
			if(N-1 >= 0 && check[N-1] == 0) {
				q.add(N-1);
				check[N-1] = check[N]+1;
			}
			
			if(N*2 <= 100000 && check[N*2] == 0) {
				q.add(N*2);
				check[N*2] = check[N]+1;
			}
		}
		System.out.println(check[K]-1);
		
	}
}