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

난이도

실버 5

문제

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

풀이

그래프 탐색, BFS로 해결

1697번 숨바꼭질에서 약간의 변형이 있는데 순간이동을 0초 후에 *2만큼 한다는 것이다.

순간이동할 때는 시간이 흐르지 않으므로 1초후에 발생하는 로직과 분리해서 처리한다.

-1, +1 하는 위치를 구하기 전에 2인 위치를 먼저 계산했다.
여기서 포인트는 2인 위치만을 계산한게 아니라 최대 위치인 100,000까지 전부 계산해둬야한다.

코드

package 그래프탐색;


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

public class BOJ13549 {
    static int n, k;
    static int[] arr;
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());


        if (n >= k) {
            System.out.println(n - k);
        } else {
            System.out.println(bfs());
        }

    }

    static int bfs() {

        arr = new int[100001];
        Arrays.fill(arr, -1);
        q.add(n);
        arr[n] = 0;
        while (!q.isEmpty()) {
            int x = q.poll();

            if (x == k)
                return arr[x];

            int tmp = x * 2;
            while (tmp <= 100000 && arr[tmp] == -1) {
                arr[tmp] = arr[x];
                q.add(tmp);
                tmp *= 2;
            }
            for (int i = 0; i < 2; i++) {
                int nx;
                if (i == 0)
                    nx = x - 1;
                else
                    nx = x + 1;

                if (nx >= 0 && nx < 100001 && arr[nx] == -1) {
                    arr[nx] = arr[x] + 1;
                    q.add(nx);
                }
            }
        }
        return 0;
    }

}