[JAVA] 백준 13549 숨바꼭질3

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

문제분석

이 문제는 다음과 같은 이동을 합니다:
x - 1
x + 1
x * 2

즉, 간선 가중치가 0 또는 1 입니다.일반 BFS는 모든 간선 가중치가 동일할 때만 최단거리를 보장합니다. 따라서 이 문제는 0-1 BFS로 풀어야 합니다.

 

 

int[] dist = new int[100_001];

 

dist[x]의 의미는:시작점 N에서 x까지 가는 최소 시간 입니다.

자바에서 int 배열은 기본값이 0입니다.하지만 우리는 이런 비교를 합니다: if(dist[next] > 새 거리) 따라서 초기값을 반드시 무한대로 설정해야 합니다. 따라서 Deque를 사용합니다.
0 앞 (offerFirst)
1 뒤 (offerLast)

이렇게 하면 큐 내부가 자동으로 거리 기준 정렬 상태를 유지합니다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken()); // 목적지

        int[] dist = new int[100_001]; // idx 칸에 가는 데 걸리는 시간 최소값
        Arrays.fill(dist, Integer.MAX_VALUE); // 0-1 BFS이므로, 시간비교를 위해 최대값으로 초기화
        ArrayDeque<Integer> q = new ArrayDeque<>();

        q.offer(N);
        dist[N] = 0;

        while(true){
            int cur = q.poll();
            if(cur == K){
                System.out.println(dist[cur]);
                return;
            }

            // +1이랑 -1은 시간 1초 추가해야 함
            int[] nArr = {cur + 1, cur - 1};
            for(int n : nArr){
                if(n >= 0 && n <= 100_000 && dist[n] > dist[cur] + 1){ // cur + 1초 보다 n가는게 더 걸리면, cur에서 1초 써서 n 가는게 더 빠르니 업데이트
                    dist[n] = dist[cur] + 1;
                    q.offer(n);
                }
            }

            // *2는 시간 소모 안함
            if(cur * 2 <= 100_000 && cur * 2 >= 0 && dist[cur * 2] > dist[cur]){
                dist[cur * 2] = dist[cur];
                q.offerFirst(cur * 2);
            }
        }
        

    }

}