[백준 JAVA] 1865번: 웜홀 (벨만-포드 풀이 + 플로이드 워셜 풀이)

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

 

문제 접근

문제를 처음 보면 단순한 최단 경로 문제처럼 보이지만 실제로는 음수 사이클의 존재 여부를 판별하는 문제다.

 

도로는 양방향으로 이동할 수 있고 시간이 양수로 흐르지만 웜홀은 단방향이며 시간을 되돌리는 효과가 있어 음수 가중치로 처리된다.

 

결국 어떤 지점에서 출발하든 다시 자기 자신으로 돌아왔을 때 전체 시간이 음수가 되는 경로가 존재하면 시간 여행이 가능하다고 볼 수 있고, 이 경우 정답은 YES가 된다.

 

풀이 방법

음수 사이클이 존재하는 최단거리 문제는 다익스트라로 풀 경우 무한 사이클이 돌아 오류가 발생하기 때문에 벨만-포드나 플로이드 워셜로 풀어햐한다.

 

먼저 플로이드 워셜로 접근한 이유부터 정리해보면 이 문제는 특정 시작점에서 다른 정점까지의 최단 거리 자체가 중요한 것이 아니라 전체 그래프 안에 음수 사이클이 있는지를 판별하는 것이 핵심이다. 플로이드 워셜은 모든 정점 쌍에 대한 최단 거리를 구하므로 연산이 끝난 뒤 자기 자신으로 가는 최단 거리가 음수가 되었는지만 보면 된다. 개념적으로는 굉장히 직관적이다.

 

플로이드 워셜 풀이의 기본 흐름은 다음과 같다.

1. 먼저 인접 행렬을 만들고 자기 자신으로 가는 거리는 0, 나머지는 INF로 초기화한다.

2. 이후 도로는 양방향 간선으로 웜홀은 단방향 음수 간선으로 반영한다.

3. 그 다음 중간 정점 k를 하나씩 거쳐 가며 최단 거리를 갱신한다.

4. 마지막에 어떤 i에 대해 graph[i][i] < 0이라면 음수 사이클이 존재한다고 판단할 수 있다.

 

코드

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

public class Main {
    static int T, N, M, W;
    static int[][] graph;
    static final int INF = 10_000_000;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());

            graph = new int[N + 1][N + 1];
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) continue;
                    graph[i][j] = INF;
                }
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());
                graph[S][E] = Math.min(graph[S][E], T);
                graph[E][S] = Math.min(graph[E][S], T);
            }

            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());
                graph[S][E] = Math.min(graph[S][E], -T);
            }

            for (int k = 1; k <= N; k++) {
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= N; j++) {
                        if (graph[i][k] < INF && graph[k][j] < INF) {
                            if (graph[i][j] > graph[i][k] + graph[k][j]) {
                                graph[i][j] = graph[i][k] + graph[k][j];
                            }
                        }
                    }
                }
            }

            sb.append(isMinusRoute()).append('\n');
        }

        System.out.println(sb);
    }

    private static String isMinusRoute() {
        for (int i = 1; i <= N; i++) {
            if (graph[i][i] < 0) {
                return "YES";
            }
        }
        return "NO";
    }
}

 

하지만 직접 풀어보면서 플로이드 워셜은 생각보다 시행착오가 많았다.

 

치명적인 실수는 INF 체크 없이 갱신하는 것이었다. 예를 들어 graph[i][k]가 INF이고 graph[k][j]가 음수라면, 도달할 수 없는 경로임에도 불구하고 INF + 음수가 INF보다 작아져 잘못된 갱신이 발생할 수 있다.

 

실제로 이 문제는 웜홀 때문에 음수 간선이 존재하므로 이런 오류가 더 쉽게 드러난다.

그래서 플로이드 워셜에서는 반드시 graph[i][k] < INF && graph[k][j] < INF 조건을 넣고 갱신해야 한다.

 

디버깅 실수

도로와 웜홀을 처리할 때도 사소한 실수가 나왔다.

도로는 양방향이기 때문에 graph[S][E]와 graph[E][S]를 각각 독립적으로 최소값 처리해야 하는데, 이때 실수로 한쪽 값을 다른 쪽 비교 기준에 넣으면 비대칭적으로 잘못 들어간다.

또한 웜홀은 시간 감소이므로 -T로 넣어야 하는데 기존 가중치와 비교할 때 T로 비교해 버리면 음수 간선 처리 자체가 망가진다. 

 

시간 복잡도 면에서도 플로이드 워셜은 O(N^3)이다.

 

이 문제의 제한에서는 통과할 수 있지만 문제의 핵심이 음수 사이클 판별이라는 점을 생각하면 다소 과한 접근처럼 느껴진다.

모든 정점 쌍의 최단 거리가 필요한 것도 아닌데 굳이 전체를 다 계산하고 있는 셈이기 때문이다.

 

풀이방법 2

그래서 다시 생각해보면 이 문제는 벨만 포드로 푸는 것이 더 자연스럽다.

벨만 포드는 음수 간선이 존재하는 그래프에서 최단 거리를 구할 수 있고 무엇보다 음수 사이클을 판별하는 대표적인 알고리즘이다.

 

모든 간선을 N-1번 완화한 뒤 한 번 더 완화가 가능하다면 음수 사이클이 존재한다고 판단한다.

이 문제의 목적과 정확히 맞아떨어진다.

 

벨만 포드 풀이에서 중요한 점은 이 문제가 특정 시작점 기준 최단 거리 문제가 아니라는 것이다.

 

보통 벨만 포드는 한 정점을 시작점으로 잡고 dist[start] = 0, 나머지는 INF로 두고 시작한다.

그런데 이 문제는 그래프 어느 위치에 있든 음수 사이클만 있으면 YES여야 한다. 즉, 연결되지 않은 다른 컴포넌트 안에 음수 사이클이 있어도 잡아내야 한다.

 

이 부분을 해결하는 방법은 dist 배열을 전부 0으로 초기화하는 것이다. 이렇게 하면 사실상 모든 정점을 출발점처럼 다루게 된다. 따로 슈퍼 노드를 만들지 않아도 같은 효과를 낼 수 있고, 그래프 전체에 대해 음수 사이클을 탐지할 수 있다.

 

벨만 포드는 인접 행렬보다 간선 리스트로 구현하는 것이 훨씬 편하다.

도로는 양방향이므로 간선을 두 개 넣고, 웜홀은 단방향 음수 간선 하나만 넣으면 된다.

그 다음 모든 간선을 N번 반복해서 확인하면서 N번째 반복에서도 값이 갱신되면 음수 사이클이 존재한다고 판단한다.

 

코드

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

public class Main {
    static int TC, N, M, W;
    static List<Edge> edges;

    static class Edge {
        int from, to, cost;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        TC = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < TC; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());

            edges = new ArrayList<>();

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());

                edges.add(new Edge(S, E, T));
                edges.add(new Edge(E, S, T));
            }

            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());

                edges.add(new Edge(S, E, -T));
            }

            sb.append(hasNegativeCycle() ? "YES" : "NO").append('\n');
        }

        System.out.print(sb);
    }

    private static boolean hasNegativeCycle() {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, 0);

        for (int i = 1; i <= N; i++) {
            boolean updated = false;

            for (Edge e : edges) {
                if (dist[e.to] > dist[e.from] + e.cost) {
                    dist[e.to] = dist[e.from] + e.cost;
                    updated = true;

                    if (i == N) {
                        return true;
                    }
                }
            }

            if (!updated) break;
        }

        return false;
    }
}

 

이 풀이의 장점은 문제의 핵심을 훨씬 직접적으로 반영한다는 점이다. 우리는 최단 거리 표 전체가 필요한 것이 아니라, 음수 사이클의 존재만 알면 된다. 벨만 포드는 바로 그 목적에 맞는 알고리즘이다. 또 인접 행렬을 만들지 않고 간선만 순회하므로 구현도 간결하고, 플로이드 워셜에서 자주 발생했던 INF 처리 실수도 크게 줄어든다.

 

시간 복잡도를 비교해보면 플로이드 워셜은 O(N^3)이고, 벨만 포드는 O(N * E)이다. 이 문제에서는 N보다 간선 수가 훨씬 더 직접적인 기준이 되고, 무엇보다 음수 사이클 판별이라는 목적에 더 잘 맞는다. 성능뿐 아니라 코드의 의도도 더 명확해진다.

 

이번 문제를 풀면서 겪은 시행착오를 다시 정리해보면 크게 네 가지 정도였다. 첫째, 문제를 최단 거리 자체로 보고 접근했다는 점이다. 사실 이 문제는 “가장 짧은 시간”을 구하는 문제가 아니라 “시간이 무한히 줄어들 수 있느냐”를 보는 문제였다. 이 관점 전환이 가장 중요했다. 둘째, 플로이드 워셜에서 간선 중복 처리와 INF 처리를 놓쳤다. 알고리즘 자체는 알고 있어도 입력 처리나 예외 상황을 정확히 다루지 않으면 오답이 쉽게 나온다는 점을 다시 느꼈다. 셋째, 웜홀의 음수 처리에서 비교 기준을 잘못 잡아 디버깅이 길어졌다. 양수 T를 그대로 비교하면 안 되고 실제 그래프에 들어가는 값인 -T 기준으로 생각해야 했다. 넷째, 시작점이 없는 음수 사이클 문제에서 dist 배열을 어떻게 초기화해야 하는지 처음에는 감이 잘 오지 않았다. 평소 벨만 포드는 특정 시작점 중심으로만 익숙했기 때문에, 모든 정점을 시작점처럼 취급하는 발상이 한 번 더 필요했다.

 

결국 이 문제를 통해 느낀 점은, 알고리즘 이름을 떠올리는 것보다 먼저 문제의 본질을 정확히 파악하는 것이 더 중요하다는 것이다. 처음에는 플로이드 워셜로도 되겠다고 생각했지만, 문제의 핵심이 음수 사이클 판별이라는 점을 분명히 인식한 뒤에는 왜 벨만 포드가 정석 풀이인지 자연스럽게 이해할 수 있었다. 플로이드 워셜은 “풀 수 있는 방법”이고, 벨만 포드는 “문제 의도에 더 맞는 방법”이었다.

 

짧게 회고를 남기면, 이번 문제는 단순히 하나의 알고리즘을 외우는 것이 아니라 “이 문제가 진짜로 묻고 있는 것이 무엇인지”를 먼저 읽어내야 한다는 걸 다시 느끼게 해준 문제였다. 앞으로도 음수 간선이 보인다고 무조건 겁먹기보다, 최단 거리 문제인지, 음수 사이클 판별 문제인지부터 먼저 구분하는 습관을 가져야겠다.