문제링크

풀이

숨바꼭질 문제는 앞으로, 뒤로, 순간이동이 모두 1초가 걸리기 때문에 BFS 메서드 내에서 현재 위치가 동생의 위치에 도달하면 그 순간의 시간을 반환하고 종료하면 된다.
하지만 이 문제는 순간이동은 시간이 0초 걸리기 때문에 동생의 위치에 도달했다고 바로 메서드를 종료시키면 틀리게 된다.

큐에는 세가지 이동 후에 방문하게 될 위치를 삽입하고, 각 위치까지 도달하는데 걸리는 시간은 time 배열에 저장한다.
세가지의 이동 모두 각각 이동을 완료한 후의 위치에 방문한 적이 없거나, 방문한 적이 있더라도 현재 걸린 시간보다 오래 걸린 경우, 시간을 업데이트 해준다.

큐가 비워질 때까지 위 과정을 반복 후, time 배열에서 동생의 위치인 k 인덱스에 저장된 값을 구해주면 된다.

아래 코드에서는 방문한적이 없는 것을 표현하기 위해 0을 사용하고 처음 위치에서부터 시간을 1로 시작했기 때문에, k 인덱스에 저장된 값에서 -1을 해주었다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol13549 {
    static int n, k;
    static int[] time = new int[100001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        bfs();
        System.out.println(time[k] - 1);
    }

    public static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        time[n] = 1;

        while (!q.isEmpty()) {
            int curr = q.poll();

            if (curr + 1 >= 0 && curr + 1 <= 100000) {  //  앞으로 이동
                if (time[curr + 1] == 0 || time[curr + 1] > time[curr] + 1) {   //  아직 방문한 적 없거나, 방문했지만 시간이 더 오래 걸리는 경우
                    time[curr + 1] = time[curr] + 1;
                    q.add(curr + 1);
                }
            }
            if (curr - 1 >= 0 && curr - 1 <= 100000) {  //  뒤로 이동
                if (time[curr - 1] == 0 || time[curr - 1] > time[curr] + 1) {   //  아직 방문한 적 없거나, 방문했지만 시간이 더 오래 걸리는 경우
                    time[curr - 1] = time[curr] + 1;
                    q.add(curr - 1);
                }
            }
            if (curr * 2 >= 0 && curr * 2 <= 100000) {  //  순간이동
                if (time[curr * 2] == 0 || time[curr * 2] > time[curr]) {   //  아직 방문한 적 없거나, 방문했지만 시간이 더 오래 걸리는 경우
                    time[curr * 2] = time[curr];
                    q.add(curr * 2);
                }
            }
        }
    }
}