백준 1865 웜홀 Java: 모든 Component의 음수 Cycle 찾기

백준 1865번 ‘웜홀’은 출발한 지점으로 돌아왔을 때 시간이 과거가 되는 경로, 즉 가중치 합이 음수인 cycle이 graph 어디엔가 있는지 판단한다. 음수 edge가 있으므로 Dijkstra가 아니라 Bellman-Ford의 N번째 relaxation 여부를 사용한다.

• 백준 1865번 웜홀

왜 N번째에도 갱신되면 음수 cycle인가

정점이 N개인 graph에서 cycle이 없는 simple path는 최대 N-1개의 edge를 가진다. 최단 거리 relaxation을 N-1번 마친 뒤에도 더 작은 값이 생긴다면 어떤 정점을 반복해 방문한 경로가 더 싸졌다는 뜻이고, 그 반복 구간의 합은 음수다.

도로는 양방향 positive edge 두 개로, 웜홀은 입력 시간에 minus를 붙인 단방향 negative edge 하나로 저장한다.

disconnected graph도 한 번에 검사하기

특정 1번 정점에서만 Bellman-Ford를 시작하면 다른 component의 negative cycle을 놓칠 수 있다. 모든 정점에 비용 0으로 연결된 가상의 super source를 둔다고 생각하고, distance를 전부 0으로 초기화하면 graph 전체를 한 번에 검사할 수 있다.

우리가 필요한 것은 실제 shortest distance가 아니라 negative cycle의 존재 여부다. 모든 정점을 시작 후보로 두는 이 초기화는 각 정점에서 Bellman-Ford를 따로 실행하는 것보다 훨씬 단순하다.

Java 코드

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

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

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

    private static boolean hasNegativeCycle(
            int vertexCount,
            List<Edge> edges
    ) {
        long[] distance = new long[vertexCount + 1];

        for (int iteration = 1; iteration <= vertexCount; iteration++) {
            boolean updated = false;

            for (Edge edge : edges) {
                long nextDistance = distance[edge.from] + edge.cost;

                if (nextDistance < distance[edge.to]) {
                    distance[edge.to] = nextDistance;
                    updated = true;

                    if (iteration == vertexCount) {
                        return true;
                    }
                }
            }

            if (!updated) {
                return false;
            }
        }

        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int testCount = Integer.parseInt(reader.readLine());
        StringBuilder output = new StringBuilder();

        for (int test = 0; test < testCount; test++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            int vertexCount = Integer.parseInt(tokenizer.nextToken());
            int roadCount = Integer.parseInt(tokenizer.nextToken());
            int wormholeCount = Integer.parseInt(tokenizer.nextToken());
            List<Edge> edges = new ArrayList<>();

            for (int road = 0; road < roadCount; road++) {
                tokenizer = new StringTokenizer(reader.readLine());
                int from = Integer.parseInt(tokenizer.nextToken());
                int to = Integer.parseInt(tokenizer.nextToken());
                int cost = Integer.parseInt(tokenizer.nextToken());
                edges.add(new Edge(from, to, cost));
                edges.add(new Edge(to, from, cost));
            }

            for (int wormhole = 0; wormhole < wormholeCount; wormhole++) {
                tokenizer = new StringTokenizer(reader.readLine());
                int from = Integer.parseInt(tokenizer.nextToken());
                int to = Integer.parseInt(tokenizer.nextToken());
                int timeReduction = Integer.parseInt(tokenizer.nextToken());
                edges.add(new Edge(from, to, -timeReduction));
            }

            output.append(
                    hasNegativeCycle(vertexCount, edges) ? "YES" : "NO"
            ).append('\n');
        }

        System.out.print(output);
    }
}

원문 풀이에서 줄어든 반복

원문은 Bellman-Ford를 몰라 약 2시간 30분 동안 씨름하다 검색과 강의로 학습했다고 적혀 있다. graph 전체의 cycle을 찾기 위해 시작점을 1부터 N까지 바꾸며 Bellman-Ford를 반복했다.

가상 super source를 사용하면 한 번의 N-round relaxation으로 모든 component를 포함한다. 시간 복잡도는 O(VE), edge list와 distance 공간은 O(V+E)다. N번째 round 전에 update가 사라지면 더 바뀔 거리가 없으므로 바로 NO를 반환한다.

non-negative edge만 있는 shortest path와 차이를 보려면 백준 1916 Dijkstra, 모든 정점 쌍을 구하는 접근은 백준 14938 Floyd-Warshall에서 비교할 수 있다.

검증 범위

Java source를 수동 검토하고 disconnected negative cycle, negative edge만 있고 cycle은 없는 graph, positive cycle과 작은 random weighted graph를 all-pairs diagonal negativity oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.