[백준] 1697번 : 숨바꼭질

문제

수빈이의 위치와 동생의 위치가 주어졌을 때

수빈이가 동생을 찾기까지 걸리는 가장 빠른 시간을 구하는 문제

 

수빈이는 1초마다 좌우로 한 칸 이동하거나

순간 이동하여 현재 위치 * 2만큼 이동할 수 있다.

 

접근 방식

DFS 혹은 BFS를 이용해서 풀 수 있는 문제로 BFS로 풀어보겠다.

 

기존에 풀던 BFS 문제와는 다르게 2차원 배열이 주어지지 않았는데

2차원 배열에서는 현재 위치에서 상하좌우로 탐색을 했다면

이번에는 현재 위치에서 좌우로 한 칸 혹은 현재 위치 * 2만큼

이동하면서 탐색하면 된다.

 

BFS에서 큐는 먼저 방문한 순서대로 정렬되기 때문에

동생의 위치에 처음 방문했을 때 시간을 기록하고

반복문을 종료하면 가장 빠르게 방문할 수 있는 시간을 알 수 있다.

 

풀이

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());

		int[] road = new int[200002];

		Queue<Integer> queue = new ArrayDeque<>();
		queue.offer(n);
		road[n] = 1;

		if (n == k && n == 0) {
			System.out.println(0);
			return;
		}

		while (road[k] == 0) {
			int cur = queue.poll();
			int x = 0;

			for (int i = 0; i < 3; i++) {
				switch (i) {
					case 0: {
						x = cur - 1;
						break;
					}
					case 1: {
						x = cur + 1;
						break;
					}
					case 2: {
						x = cur * 2;
						break;
					}
				}

				if (x < 0 || x >= 200002) continue;
				if (road[x] > 0) continue;

				queue.offer(x);
				road[x] = road[cur] + 1;
			}
		}

		System.out.println(road[k] - 1);
	}
}