백준 1916 최소비용 구하기 Java: PriorityQueue 다익스트라

백준 1916번 ‘최소비용 구하기’는 방향 그래프에서 한 출발 도시부터 한 도착 도시까지의 최소 버스 비용을 구한다. 간선 비용이 음수가 아니므로 인접 리스트와 PriorityQueue를 사용한 다익스트라 알고리즘을 적용할 수 있다.

• 백준 1916번 최소비용 구하기

heap에는 지금까지의 총비용을 넣는다

각 상태는 (도시, 출발점부터 그 도시까지의 비용)으로 둔다. heap에서 비용이 가장 작은 상태를 꺼내고, 현재 도시를 거쳐 이웃 도시로 가는 비용이 기존 기록보다 작으면 완화한다.

nextCost = currentCost + edgeCost

Java PriorityQueue에는 이미 들어간 원소의 priority를 직접 낮추는 연산이 없다. 더 짧은 경로를 찾을 때 새 상태를 다시 넣고, 나중에 예전 상태를 꺼내면 currentCost != distance[current] 조건으로 버린다.

도착 도시가 최소비용 상태로 heap에서 나온 순간에는 답이 확정됐으므로 탐색을 끝내도 된다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static class Edge {
        private final int to;
        private final int cost;

        private Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    private static class State implements Comparable<State> {
        private final int city;
        private final long cost;

        private State(int city, long cost) {
            this.city = city;
            this.cost = cost;
        }

        @Override
        public int compareTo(State other) {
            return Long.compare(this.cost, other.cost);
        }
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );

        int cityCount = Integer.parseInt(reader.readLine());
        int busCount = Integer.parseInt(reader.readLine());

        List<Edge>[] graph = new ArrayList[cityCount + 1];
        for (int city = 1; city <= cityCount; city++) {
            graph[city] = new ArrayList<>();
        }

        for (int bus = 0; bus < busCount; bus++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            int from = Integer.parseInt(tokenizer.nextToken());
            int to = Integer.parseInt(tokenizer.nextToken());
            int cost = Integer.parseInt(tokenizer.nextToken());

            graph[from].add(new Edge(to, cost));
        }

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int start = Integer.parseInt(tokenizer.nextToken());
        int destination = Integer.parseInt(tokenizer.nextToken());

        long[] distance = new long[cityCount + 1];
        Arrays.fill(distance, Long.MAX_VALUE);
        distance[start] = 0;

        PriorityQueue<State> queue = new PriorityQueue<>();
        queue.offer(new State(start, 0));

        while (!queue.isEmpty()) {
            State current = queue.poll();

            if (current.cost != distance[current.city]) {
                continue;
            }

            if (current.city == destination) {
                break;
            }

            for (Edge edge : graph[current.city]) {
                long nextCost = current.cost + edge.cost;

                if (nextCost < distance[edge.to]) {
                    distance[edge.to] = nextCost;
                    queue.offer(new State(edge.to, nextCost));
                }
            }
        }

        System.out.println(distance[destination]);
    }
}

원문 code의 comparator는 o1[1] - o2[1] 형태였다. 값의 차이를 빼서 비교하면 범위가 커질 때 overflow로 순서가 뒤집힐 수 있으므로 Long.compare()를 사용했다. distance와 덧셈도 long으로 계산해 입력 범위가 바뀌어도 중간 합이 쉽게 넘치지 않게 했다.

예제 실행

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

1 → 4 → 5의 비용은 1 + 3 = 4다. 1 → 3 → 5도 3 + 1 = 4이므로 최소비용은 4다.

4

복잡도와 자주 놓치는 점

성공적인 완화마다 heap에 새 상태가 들어갈 수 있어 중복 entry는 최악에 O(M)개 생길 수 있다. 이 구현의 시간 복잡도는 O((N + M) log M), 공간 복잡도는 O(N + M)으로 볼 수 있다.

• 버스는 방향 간선이므로 반대 방향을 자동으로 추가하지 않는다.
• 같은 도시 쌍을 잇는 버스가 여러 개여도 모두 인접 리스트에 넣어도 된다.
• 방문 boolean만 보고 처음 만난 도시를 확정하면 안 된다. 최소비용 상태가 heap에서 나왔는지 확인한다.

모든 정점까지의 거리를 출력하는 형태는 백준 1753 최단경로, 최소비용 경로 자체까지 복원하는 문제는 백준 11779 최소비용 구하기 2에서 이어서 볼 수 있다.

Java source를 수동 검토하고 보존된 예제 및 random directed graph 100개를 Floyd-Warshall oracle과 대조했다. 2026년 8월 2일 현재 BOJ 문제 URL은 채점 서비스 준비 화면이라 current judge 재제출은 확인하지 못했다.