[백준] 1865번 - 웜홀 (Gold 3)

문제 링크

백준 1865번 - 웜홀 (Gold 3)

문제 설명

N($\leq$ 500)개의 지점 사이를 잇는 M + W($\leq$ 2,700)개의 도로가 있다.
도로의 출발 지점과 도착 지점 및 이동하는데 걸리는 시간이 주어져 있는데, 이동시간은 음수일 수도 있다.
출발 위치로 돌아오는 음의 사이클이 존재한다면 YES를, 아니라면 NO를 출력하시오.

정답 코드 및 설명

음의 가중치를 가지는 간선이 존재할 때의 최단 거리를 찾는 벨만-포드 알고리즘을 응용하면 된다.
벨만-포드 알고리즘은 원래 최단 거리를 구하는 알고리즘이지만, 마지막에 음의 사이클이 존재하는지 여부를 체크하게 된다.

하지만, 벨만-포드 알고리즘은 출발 지점이 정해져 있을 때 수행하는 알고리즘이다.
만약 그래프가 연결 그래프가 아니라면, 벨만-포드 알고리즘을 한 번 수행해서는 모든 음의 사이클이 존재하는지를 확인할 수 없게 된다. 출발 지점과 연결되어 있지 않은 영역에 음의 사이클이 있을 가능성도 있기 때문이다.

이는 더미 노드를 추가하고 모든 노드에 대해 더미 노드에서 출발하여 각 노드로 가는 가중치 0인 간선을 추가한 후, 더미 노드에서 시작하는 벨만-포드 알고리즘을 돌림으로써 해결이 가능하다. 이렇게 하면 그래프가 연결 그래프가 됨은 자명하다. 또한 노드 i에서 노드 j로 가는 것을 더미 노드에서 노드 i로 갔다가 노드 j로 가는 것으로 생각할 수 있는데, 더미 노드에서 노드 i로 가는 간선의 가중치는 0이므로 벨만-포드 알고리즘의 동작에 영향을 주지도 않는다.

물론, 더미 노드를 추가하지 않고 각 연결 요소마다 벨만-포드 알고리즘을 돌리는 방식으로도 해결이 가능하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1865 {
    static final int INF = 10_000_000;
    int n;
    ArrayList<Edge> time;

    static class Edge {
        int start, end, time;

        public Edge(int start, int end, int time) {
            this.start = start;
            this.end = end;
            this.time = time;
        }
    }

    void input(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        time = new ArrayList<>();
        setRoads(m, br);
        setWormHoles(w, br);
        for (int i = 1; i <= n; i++)
            time.add(new Edge(0, i, 0));
    }

    void setRoads(int m, BufferedReader br) throws IOException {
        StringTokenizer st;
        int s, e, t;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            t = Integer.parseInt(st.nextToken());
            time.add(new Edge(s, e, t));
            time.add(new Edge(e, s, t));
        }
    }

    void setWormHoles(int w, BufferedReader br) throws IOException {
        StringTokenizer st;
        int s, e, t;
        for (int i = 0; i < w; i++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            t = -Integer.parseInt(st.nextToken());
            time.add(new Edge(s, e, t));
        }
    }

    boolean BellmanFord() {
        int[] minTime = new int[n + 1];
        Arrays.fill(minTime, INF);
        minTime[0] = 0;
        for (int k = 1; k <= minTime.length; k++) {
            for (Edge e : time) {
                if (minTime[e.start] == INF) continue;
                if (minTime[e.start] + e.time < minTime[e.end]) {
                    if (k == minTime.length) return true;
                    minTime[e.end] = minTime[e.start] + e.time;
                }
            }
        }
        return false;
    }

    String answer() {
        if (BellmanFord()) return "YES";
        return "NO";
    }

    void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while (tc-- > 0) {
            input(br);
            System.out.println(answer());
        }
    }

    public static void main(String[] args) throws IOException {
        new BOJ1865().solution();
    }
}