백준 1697번: 숨바꼭질

현재위치가 x라고 했을 때,

x-1
x+1
2*x

를 반복해서 수빈 위치(start)에서 동생 위치(end)까지 최소 몇 번 만에 갈 수 있는지 구해야한다.
따라서 BFS를 사용하면 된다.

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

public class Main {
	static int start;
	static int end;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		visited = new boolean[100000 + 1];

		start = Integer.parseInt(st.nextToken()); // 수빈이 위치
		end = Integer.parseInt(st.nextToken()); // 동생 위치
		int cnt = bfs(start, end);

		bw.write(String.valueOf(cnt));
		bw.flush();
		bw.close();
	}

	private static int bfs(int start, int end) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		visited[start] = true; // 방문 처리

		int cnt = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int curr = queue.poll();
				if (curr == end) {
					return cnt;
				}
				// x-1로 이동
				if (curr - 1 >= 0 && !visited[curr - 1]) {
					queue.add(curr - 1);
					visited[curr - 1] = true;
				}
				// x+1로 이동
				if (curr + 1 <= 100000 && !visited[curr + 1]) {
					queue.add(curr + 1);
					visited[curr + 1] = true;
				}
				// 2*x로 이동
				if (curr * 2 <= 100000 && !visited[curr * 2]) {
					queue.add(curr * 2);
					visited[curr * 2] = true;
				}
			}
			cnt++;
		}
		return -1; // 이 부분은 논리적으로 도달하지 않음
	}
}