백준 1238 파티 Java: 정방향·역방향 Dijkstra 두 번

백준 1238번 ‘파티’는 각 학생이 자기 마을에서 X번 마을까지 갔다가 돌아오는 최단시간 중 최댓값을 구한다. 모든 마을을 시작점으로 Dijkstra를 실행할 수도 있지만, 원래 graph와 간선을 뒤집은 graph에서 X를 시작점으로 한 번씩 실행하면 두 번으로 줄일 수 있다.

• 백준 1238번 파티

간선을 뒤집으면 i에서 X까지가 X에서 i까지가 된다

원래 graph에서 다음 경로가 있다고 하자.

i → a → b → X

모든 간선 방향을 뒤집으면 같은 비용의 경로가 다음처럼 된다.

X → b → a → i

따라서 다음 두 distance array를 얻을 수 있다.

• original graph에서 X 출발: X → i 귀가 시간
• reversed graph에서 X 출발: original의 i → X 파티행 시간

각 마을에서 두 값을 더한 뒤 최댓값을 구한다.

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 vertex;
        private final long distance;

        private State(int vertex, long distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

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

    private static long[] dijkstra(List<Edge>[] graph, int start) {
        long[] distance = new long[graph.length];
        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.distance != distance[current.vertex]) {
                continue;
            }

            for (Edge edge : graph[current.vertex]) {
                long nextDistance = current.distance + edge.cost;

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

        return distance;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int vertexCount = Integer.parseInt(tokenizer.nextToken());
        int edgeCount = Integer.parseInt(tokenizer.nextToken());
        int party = Integer.parseInt(tokenizer.nextToken());

        @SuppressWarnings("unchecked")
        List<Edge>[] graph = new ArrayList[vertexCount + 1];
        @SuppressWarnings("unchecked")
        List<Edge>[] reversed = new ArrayList[vertexCount + 1];

        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            graph[vertex] = new ArrayList<>();
            reversed[vertex] = new ArrayList<>();
        }

        for (int edge = 0; edge < edgeCount; edge++) {
            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));
            reversed[to].add(new Edge(from, cost));
        }

        long[] fromParty = dijkstra(graph, party);
        long[] toParty = dijkstra(reversed, party);
        long answer = 0;

        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            answer = Math.max(
                    answer,
                    toParty[vertex] + fromParty[vertex]
            );
        }

        System.out.println(answer);
    }
}

원문 PriorityQueue 기준의 오류

원문 queue에는 {vertex, distance}를 넣었지만 comparator는 첫 번째 값인 vertex number를 비교했다. stale entry를 반복 처리해 결과가 나올 수는 있어도, “현재 distance가 가장 작은 state를 먼저 확정한다”는 Dijkstra의 queue 조건을 만족하지 않는다.

새 구현은 State.distance를 Long.compare()로 비교한다. distance가 현재 array 값과 다른 stale state는 건너뛴다. 문제는 각 학생이 X에 갔다가 돌아올 수 있다고 보장하지만, 일반화한 code에서는 Long.MAX_VALUE를 더하기 전에 reachable 여부를 확인해야 한다.

N번 대신 두 번이라는 관찰

원문에는 각 마을에서 X로 가는 Dijkstra N-1번과 X에서 모든 마을로 가는 한 번, 총 N번의 방법과 reverse graph를 써서 두 번 실행하는 방법을 함께 적었다. 핵심은 reverse graph의 X → i가 original graph의 i → X와 같은 path cost라는 점이다.

한 시작점·한 목적지의 기본형은 백준 1916 최소비용 구하기, 실제 route까지 복원하는 형태는 백준 11779 최소비용 구하기 2에서 이어진다.

두 번의 Dijkstra 시간은 O((V+E) log E), 두 adjacency list와 heap 공간은 O(V+E)다.

검증 범위

Java source를 수동 검토하고 asymmetric directed graph, parallel edge와 작은 random strongly connected graph를 각 vertex에서 실행한 all-source shortest paths와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.