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

접근

BFS를 이용하여 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구할 수 있습니다.

 

코드

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

public class Main {
	static int n, k;
	static int[] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력 처리
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		visited = new int[100001];

		// 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하기 위해서 bfs를 이용한다.
		int minTime = bfs();

		// 결과 출력
		System.out.println(minTime);
	}

	static int bfs() {
		Queue<Integer> bfsQ = new ArrayDeque<>();
		bfsQ.offer(n);

		while (!bfsQ.isEmpty()) {
			Integer curr = bfsQ.poll();

			// 동생을 찾은 경우
			if (curr == k) {
				return visited[curr];
			}

			// -1 이동
			if (canGo(curr - 1)) {
				visited[curr - 1] = visited[curr] + 1;
				bfsQ.offer(curr - 1);
			}
			// +1 이동
			if (canGo(curr + 1)) {
				visited[curr + 1] = visited[curr] + 1;
				bfsQ.offer(curr + 1);
			}
			// 순간이동
			if (canGo(2 * curr)) {
				visited[2 * curr] = visited[curr] + 1;
				bfsQ.offer(2 * curr);
			}
		}

		return -1;
	}

	static boolean canGo(int x) {
		return (0 <= x && x <= 100000) && visited[x] == 0;
	}
}