문제

이해

N개의 지점과 지점 사이를 잇는 M개의 도로와 W개의 웜홀이 존재한다.

도로는 양방향 이동이 가능하고 웜홀은 단방향으로만 이동이 가능하다.

도로를 통해서 이동할 때는 당연하게도 시간이 가지만 웜홀을 통해 이동한다면 시간이 뒤로 가게 된다.

위와 같은 (무방향과 방향이 섞인)그래프가 주어질 때 시간이 줄어들면서 출발한 위치로 돌아올 수 있다면 YES, 아니라면 NO를 출력한다.

접근

결론부터 말하자면 이 문제는 벨만 포드 알고리즘에 대한 문제이다.

나는 벨만 포드를 알지 못했기 때문에 최단 경로 문제를 데이크스트라로 접근했다.

데이크스트라는 시작점을 기준으로 최단 경로를 계산한다.

문제에서는 출발점으로 다시 돌아와야 하기 때문에 특정 지점으로 갔다가 돌아오는 왕복 시간이 음수라면 YES를 반환하면 될 것이라고 생각했다.

물론 출발점이 따로 주어지지 않았기 때문에 1부터 N까지 모든 지점에 대해 데이크스트라를 두번씩 (왕복이기 때문) 해야 했다.

이렇게 생각한 시점부터 정말 복잡한 코드를 작성해야함과 시간복잡도가 클 것이라는 예상을 했으며 머지않아 놓친 부분이 있었다는 것을 알게 되었다.

음의 가중치를 포함한 그래프에서는 최단 경로가 불가능할 수도 있다는 것이다.

왜냐하면 만일 그래프 상에서 가중치의 합이 음수인 사이클이 발생한다면?

위의 예제는 정점 2,3에서 음의 사이클이 발생하는 경우이다. 이 경우에서 최단 경로를 구할 수 있을까?

단연코 없다. 왜냐하면 2-3의 사이클을 통과할수록 가중치는 0을 넘어 더 작아지기 때문에 이 때의 최단경로는 -INF가 되는 것이다.

데이크스트라는 정점을 방문하면서 DP로 값을 수정한다.

이 때, 순환을 돌면서 가중치가 계속 작아지기 때문에 이 경우 데이크스트라를 적용할 수 없는 것이다.

최단 경로를 검색하던 중 벨만 포드 알고리즘에 대해서 알게 되었다.

벨만 포드 알고리즘을 간단히 요약하자면 그래프 상의 간선들을 그 개수만큼 반복해서 계속 조사하면서 relaxation을 수행한다.

주로 루프를 간선의 개수만큼 수행하게 되는데 만일 특정 루프 시점에서 relaxation이 수행되지 않았다면 더 이상 조사할 필요가 없으므로 최단 경로가 모두 계산되었다는 의미이다.

벨만 포드 알고리즘에 대해서는 나중에 자세하게 포스팅해볼 예정이다.

그렇다면 벨만 포드 알고리즘에서의 음의 사이클은 어떨까? 음의 사이클이 존재한다면 최단 경로를 구할 수 없는 것은 자명하다.

하지만 우리는 벨만 포드 알고리즘을 통해 그래프 상에 음의 사이클이 존재하는 지 알 수 있다.

벨만 포드 알고리즘은 전체 간선에 대한 조사를 그 개수만큼 수행하는데 만일 그 이상 조사를 반복할 때까지 relaxation이 발생한다면?

이 말은 최단 경로가 계속 음수로 수정된다는 이야기이고 다시 말해 음의 사이클이 존재한다는 의미이다.

따라서, 이 문제는 벨만 포드 알고리즘을 적용하여 그래프 상에 음의 사이클이 존재하는 지 알아보는 문제이다.

존재한다면 YES (과거로 돌아갈 수 있다.) 존재하지 않는다면 NO (일반적인 최단경로를 구할 수 있다.)

코드

package java_baekjoon;

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

public class prob1865 {
    static class edge {
        int node1;
        int node2;
        int sec;

        public edge(int node1, int node2, int sec) {
            this.node1 = node1;
            this.node2 = node2;
            this.sec = sec;
        }
    }

    final static int MAX = Integer.MAX_VALUE;
    static int T;
    static int N;
    static int M;
    static int W;
    static edge[] arr_road;
    static edge[] arr_wormhole;
    static boolean flag;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        while (T-- > 0) {
            flag = false;
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            arr_road = new edge[M];
            W = Integer.parseInt(st.nextToken());
            arr_wormhole = new edge[W];

            //도로 입력
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int node1 = Integer.parseInt(st.nextToken());
                int node2 = Integer.parseInt(st.nextToken());
                int sec = Integer.parseInt(st.nextToken());
                arr_road[i] = new edge(node1, node2, sec);
            }
            //웜홀 입력
            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int node1 = Integer.parseInt(st.nextToken());
                int node2 = Integer.parseInt(st.nextToken());
                int sec = Integer.parseInt(st.nextToken());
                arr_wormhole[i] = new edge(node1, node2, sec);
            }

            for (int i = 1; i <= N; i++) {
                if (Bellman_Ford(i)) {
                    flag = true;
                    break;
                }
            }

            if (flag) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    static boolean Bellman_Ford(int start) {
        int[] min_sec = new int[N + 1];
        Arrays.fill(min_sec, MAX);
        min_sec[start] = 0;

        //모든 간선의 개수 + 1 만큼 반복
        for (int i = 0; i <= M + W; i++) {
            //수정 여부 변수
            boolean update = false;

            //road edge relaxation(no direction)
            for (int j = 0; j < M; j++) {
                int node1 = arr_road[j].node1;
                int node2 = arr_road[j].node2;
                if (min_sec[node1] == MAX && min_sec[node2] == MAX) {
                    continue;
                }
                if (min_sec[node1] != MAX) {
                    int sec = min_sec[arr_road[j].node1] + arr_road[j].sec;
                    if (sec < min_sec[arr_road[j].node2]) {
                        min_sec[arr_road[j].node2] = sec;
                        update = true;
                    }
                }
                if (min_sec[node2] != MAX) {
                    int sec = min_sec[arr_road[j].node2] + arr_road[j].sec;
                    if (sec < min_sec[arr_road[j].node1]) {
                        min_sec[arr_road[j].node1] = sec;
                        update = true;
                    }
                }
            }

            //wormhole edge relaxation(direction)
            for (int j = 0; j < W; j++) {
                int node1 = arr_wormhole[j].node1;
                if (min_sec[node1] == MAX) {
                    continue;
                }
                int sec = min_sec[arr_wormhole[j].node1] - arr_wormhole[j].sec;
                if (sec < min_sec[arr_wormhole[j].node2]) {
                    min_sec[arr_wormhole[j].node2] = sec;
                    update = true;
                }
            }

            //수정이 없다면 음수 사이클이 없음
            if (!update) {
                return false;
            }
        }

        //지속적으로 수정이 발생하여 M+W+1만큼 조사했을 때 음수 사이클 발생
        return true;
    }
}

루프마다 수정이 발생하면 계속 반복하고 아니라면 모든 최적화가 완료됐다는 의미이므로 중단한다.

결과