[1697] 백준 - 숨바꼭질(JAVA)

- Queue에 들려야 하는 위치를 계속 넣어주는 BFS방법을 이용하여 풀었다.

 

 

- 동생한테 가는 방법은 [ X + 1 ] , [ X - 1 ] , [ X * 2 ] 이렇게 3가지이다.

- 동생의 현재 위치가 최대 100000이지만, 100002에서 오는 경우 등 최대 수를 넘을 수도 있다고 생각하여,
   넉넉하게 배열을 200001로 크기를 주었다.

- 다음에 방문할 곳이( X + 1  ,  X - 1  ,  X * 2 ) 
   0보다 크고, 배열 최대 크기보다 작다면 탐색을 해보아야 하는 곳으로 정하고
   방문 처리를 한 후, queue에 넣어주었다.

 

- 동생을 찾으면 isFind를 true로 해주어, 더이상 탐색하지 않도록 하였다.

 

- 소요된 시간은 time에 +해주었다.

 

 

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 N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		boolean road[] = new boolean[200001];
		road[N] = true; // 방문처리

		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(N);

		int time = 0;
		boolean isFind = false;
		while (!queue.isEmpty() && !isFind) {
			int size = queue.size();

			while (--size >= 0 && !isFind) {
				int num = queue.poll();

				if (num == K) {
					isFind = true;
					break;
				}

				if (num > 0 && !road[num - 1]) {
					queue.offer(num - 1);
					road[num - 1] = true;
				}

				if (num + 1 < 200000 && !road[num + 1]) {
					queue.offer(num + 1);
					road[num + 1] = true;
				}

				if (num * 2 < 200000 && !road[num * 2]) {
					queue.offer(num * 2);
					road[num * 2] = true;
				}
			}

			time++;
		}
		System.out.println(time - 1);

	}

}