[백준] | JAVA, 자바 | 1697번 - 숨바꼭질

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

---

문제 요약 :

1. 수빈이가 있는 위치 N과 동생이 있는 위치 K 입력받기

2. 수빈이의 위치가 x 일 때 걷는다면 1초 후에 x - 1 또는 X + 1로 이동

3. 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동

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

---

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

public class Main {
    private static int N, K;
    private static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 1. 수빈이가 있는 위치 N과 동생이 있는 위치 K 입력받기
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        // 동생의 위치가 최대 100,000이기 때문에 100001로 생성
        visited = new boolean[100001];
        // 4. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지 구하는 프로그램 작성
        System.out.println(find());
    }

    private static int find() {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(N);
        int cnt = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int temp = queue.poll();

                if (temp == K) return cnt;

                // 2. 수빈이의 위치가 x 일 때 걷는다면 1초 후에 x - 1 또는 X + 1로 이동
                // 3. 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동
                int[] next = {temp - 1, temp + 1, temp * 2};

                for (int idx : next) {
                    if (idx >= 0 && idx <= 100000 && !visited[idx]) {
                        visited[idx] = true;
                        queue.add(idx);
                    }
                }
            }
            cnt++;
        }
        return -1;
    }
}