[백준] 1697 숨바꼭질

---

https://smartpro.tistory.com/18

[백준/1697/Java] 숨바꼭질 - BFS 풀이

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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