Baekjoon #13549 숨바꼭질3 (java, 다익스트라, 우선순위큐)

접근 방법

이 문제는 간선의 비용이 다르기 때문에 특정 노드(목표치)까지 최단거리를 찾기 위해서는 BFS가 아닌 다익스트라 알고리즘을 사용해야한다.

다익스트라 알고리즘은 큐에 새로운 노드를 넣을 때 마다 노드들을 비용기준 오름차순으로 정렬하고, 가장 비용이 적은 노드를 꺼내며 최단거리를 갱신한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int N, K;
    static int[] distance = new int[100001];
    static PriorityQueue<Point> locaQ = new PriorityQueue<>();


    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        for (int i = 0; i < 100001; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        find();
        System.out.println(distance[K]);
    }

    private static void find() {
        locaQ.offer(new Point(N, 0));
        distance[N] = 0;
        while (!locaQ.isEmpty()) {
            Point curL = locaQ.poll();

            int nx, cost;

            nx = curL.x + 1;
            cost = curL.y + 1;
            if (nx <= 100000 && cost < distance[nx]) {
                distance[nx] = cost;
                locaQ.offer(new Point(nx, cost));
            }

            nx = curL.x - 1;
            cost = curL.y + 1;
            if (0 <= nx && cost < distance[nx]) {
                distance[nx] = cost;
                locaQ.offer(new Point(nx, cost));
            }

            nx = curL.x * 2;
            cost = curL.y;
            if (nx <= 100000 && cost < distance[nx]) {
                distance[nx] = cost;
                locaQ.offer(new Point(nx, cost));
            }

        }
    }
    static class Point implements Comparable<Point>{
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point that) {
            if (this.y > that.y) {
                return 1;
            } else if (this.y < that.y) {
                return -1;
            }
            return 0;
        }
    }
}

참고

https://www.acmicpc.net/board/view/38887#comment-69010

글 읽기 - [13549-숨바꼭질3] BFS 큐에 넣는 순서 질문

출처

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

13549번: 숨바꼭질 3