[백준] 13549 숨바꼭질 3 - JAVA

풀이코드

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

public class Main {
    static int N, K;
    static int[] time = new int[100001];
    static boolean[] visited = new boolean[100001];
    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(0);
        } else {
            bfs(N);
        }
    }
    public static void bfs(int start) {
        Deque<Integer> dq = new LinkedList<Integer>();
        dq.add(start);
        visited[start] = true;
        time[start] = 0;

        while(!dq.isEmpty()){
            int cur = dq.poll();

            int [] nexts = {cur * 2, cur - 1, cur + 1 };
            for(int i = 0; i < 3; i++){
                int next = nexts[i];

                if(next < 0 || next > 100000 || visited[next]) continue;

                visited[next] = true;

                if(i == 0){
                    dq.addFirst(next);
                    time[next] = time[cur];
                } else if(i == 1){
                    dq.addLast(next);
                    time[next] = time[cur] + 1;
                } else{
                    dq.addLast(next);
                    time[next] = time[cur] + 1;
                }

                if(next == K){
                    System.out.println(time[next]);
                    return;
                }
            }
        }
    }

}

이전에 풀었던 순간이동 할 때 이동 시간이 1이었던 숨바꼭질 1에서 순간이동 시간이 0 으로만 바뀐 문제였다.

그래서 그냥 이동할 때마다 1 더해주던건 조건문으로 나눠서 순간이동 할때는 지금 시간 그대로 해주면 되는거 아니야? 라고 생각하고 풀었는데 그게 아니었다.

최단 시간을 찾기 위해서는 순간이동 시간이 더 짧기 때문에 순간이동 했을 때를 우선순위로 q에 넣어줘야 한다는 것을 알게 되었다.

그러면서 알게된 Deque 클래스 addFirst, addLast로 맨 뒤에 넣을지 맨 앞에 넣을지를 결정할 수 있었다.

이렇게 알게된 Queue와 Dequeue 클래스의 차이점은 다른 게시글로 적겠다.