[BOJ] 13549. 숨바꼭질 3

문제 원본 : https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String s = br.readLine();
        int n = Integer.parseInt(s.split(" ")[0]);
        int k = Integer.parseInt(s.split(" ")[1]);

        int[] arr = new int[100001];
        Arrays.fill(arr, -1);

        arr[n] = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(n);
        while (!queue.isEmpty()) {
            int curr = queue.poll();

            if (curr * 2 <= 100000 && arr[curr * 2] == -1) {
                arr[curr * 2] = arr[curr];
                queue.add(curr * 2);
            } else if (curr * 2 <= 100000 && arr[curr * 2] > arr[curr]) {
                arr[curr * 2] = arr[curr];
                queue.add(curr * 2);
            }

            if (curr - 1 >= 0 && arr[curr - 1] == -1) {
                arr[curr - 1] = arr[curr] + 1;
                queue.add(curr - 1);
            } else if (curr - 1 >= 0 && arr[curr - 1] > arr[curr] + 1) {
                arr[curr - 1] = arr[curr] + 1;
                queue.add(curr - 1);
            }

            if (curr + 1 <= 100000 && arr[curr + 1] == -1) {
                arr[curr + 1] = arr[curr] + 1;
                queue.add(curr + 1);
            } else if (curr + 1 <= 100000 && arr[curr + 1] > arr[curr] + 1) {
                arr[curr + 1] = arr[curr] + 1;
                queue.add(curr + 1);
            }
        }

        bw.write(String.valueOf(arr[k]));

        bw.close();
        br.close();
    }
}

• BFS 문제
• 순간이동은 0초를 소모하기 때문에 해당 지점에 처음 도착했다고 최소 시간이 된다고 보장하지 않는다.
• 예를 들어 입력이 4 6 일 경우,
• 4 -> 5 -> 6 순서로 방문하면 2초가 걸리지만 4 -> 3 -> 6 순서로 방문하면 1초가 걸린다.
• 따라서 최소 시간을 갱신하면 탐색해야 한다.