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

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

---

문제 풀이 :

1. 수빈이 위치 N(0 ≤ N ≤ 100,000), 동생의 위치 K(0 ≤ K ≤ 100,000) 입력 받기

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

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

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

---

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

public class Main {
    static class Move {
        int x, second;
        public Move(int x, int second) {
            this.x = x;
            this.second = second;
        }
    }
    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(0 ≤ N ≤ 100,000), 동생의 위치 K(0 ≤ K ≤ 100,000) 입력 받기
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visited = new boolean[100001];
        System.out.println(bfs());
    }

    private static int bfs() {
        Deque<Move> queue = new ArrayDeque<>();
        queue.add(new Move(N, 0));
        int cnt = 0;
        while (!queue.isEmpty()) {
            Move n = queue.poll();

            if (isRange(n.x) && !visited[n.x]) {
                // 4. 수빈이가 동생을 찾는 가장 빠른 시간을 출력
                if (n.x == K) return n.second;
                visited[n.x] = true;

                // 2. 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동
                int n1 = n.x - 1;
                int n2 = n.x + 1;
                // 3. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동
                int n3 = n.x * 2;

                if (isRange(n1)) queue.addLast(new Move(n1, n.second + 1));
                if (isRange(n2)) queue.addLast(new Move(n2, n.second + 1));
                if (isRange(n3)) queue.addFirst(new Move(n3, n.second));
            }
        }
        return cnt;
    }

    // x <= K가 아닌 x < 100001인 이유는 N이 항상 K보다 작다고 보장되지 않았음
    private static boolean isRange(int x) {
        return x >= 0 && x < 100001;
    }
}