[백준] 1695번 - 숨바꼭질

https://www.acmicpc.net/problem/1697

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N$(0 ≤ N ≤ 100,000)$에 있고, 동생은 점 K$(0 ≤ K ≤ 100,000)$에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

java 풀이

• 처음에 DFS로 풀이했었는데, 빠르게 도달한 시간이라서 BFS로 풀이해야 통과하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {

	private static int n, k;
	private static boolean[] visited;
	private static int INF = 100001;

	public static void main(String[] args) throws Exception {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] split = in.readLine().split(" ");
		n = Integer.parseInt(split[0]);
		k = Integer.parseInt(split[1]);

		visited = new boolean[INF];

		int ans = find(n);
		if (n == k) {
			ans = 0;
		}
		System.out.println(ans);
		// System.out.println(Arrays.toString(visited));

	}

	private static int[] dx = { -1, 1 };

	private static int find(int v) {

		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] { v, 0 });
		visited[v] = true;

		while (!queue.isEmpty()) {
			int[] curr = queue.poll();
			int p = curr[0];
			int time = curr[1];
			if (p == k) {
				return time;
			}

			for (int i = 0; i < 3; i++) {
				int x = 0;
				if (i < 2) {
					x = p + dx[i];
				} else {
					x = p * 2;
				}

				if (x >= INF || x < 0)
					continue;

				if (!visited[x]) {

					visited[x] = true;
					queue.offer(new int[] { x, time + 1 });
				}
			}
		}
		return -1;

	}

}