[백준] 11657번 - 타임머신 (Gold 4)

문제 링크

백준 11657번 - 타임머신 (Gold 4)

문제 설명

N개의 도시가 있다. 한 도시에서 다른 도시로 가는 버스가 M개 있는데, 버스의 운행시간은 0이거나 음수일 수도 있다. 버스의 운행시간이 0이면 순간이동을, 음수라면 타임머신을 타고 과거로 이동한 것이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 출력하시오.

단, 음의 사이클이 존재해서 어떤 도시로 갈 때 시간을 무한히 되돌아갈 수 있다면, 첫째 줄에 -1을 출력한다.
또한, 1번 도시에서 해당 도시로 가는 경로가 없다면 가장 빠른 시간 대신 해당 줄에 -1을 출력한다.

정답 코드 및 설명

음의 가중치가 가능할 때 최단거리를 찾는 문제로, 전형적인 벨만-포드 알고리즘 문제이다.
다익스트라는 모든 가중치가 0 이상일 때만 쓸 수 있으므로 이 문제에는 적용할 수 없다.

벨만-포드 알고리즘은 기본적으로 DP의 형태를 띈다.
a에서 시작해서 b에 도착하는 간선의 가중치를 w[a][b]라고 하자. 만일 해당 간선이 없다면 w[a][b] 값은 무한대로 취급한다. 이제 $a_{i}[j]$를 i개 이하의 간선을 사용해 j까지 도달하는 최단거리의 길이라고 하자.
그러면 $a_{1}[j] = w[1][j]$임은 정의에 의해 자명하다.
점화식 $a_{i + 1}[j] = \mathrm{min} \lbrace a_{i}[j], a_{i}[1] + w[1][j], a_{i}[2] + w[2][j], \cdots a_{i}[n] + w[n][j] \rbrace$이 성립함은 쉽게 보일수 있다. i개 이하의 간선을 사용한 경우에 한개의 간선을 이었을 때 어떻게 되는지를 보면 된다.

이제, 마지막으로 음의 사이클이 없는지를 검증하는 부분이 남았다.
정상적인 상황이라면 i = n - 1일 때까지만 구하면 최단 경로의 길이가 모두 구해졌을 것이다.
n개 이상의 간선을 잇는다면 무조건 사이클이 형성되기 때문이다.
따라서, i = n - 1일 때 $a_{i}[j] + w[j][k] < a_{i}[k]$인 j, k가 없는지를 확인하면 된다. 만약 있다면 음의 사이클이 형성된 것이기 때문이다.

노드가 V개, 간선이 E개인 그래프에서 벨만-포드 알고리즘을 적용했을 때 시간 복잡도를 계산해보자.
배열 $a_{i}$를 이용해서 $a_{i+1}$을 계산하려면 총 $V + E$개의 항을 비교해야한다.
위의 서술만 보면 $V + V^2$일거 같지만, 이는 행렬방식의 그래프 저장을 기준으로 서술해서 그렇고, 인접리스트로 저장한다면 뒤의 $V^2$항을 E로 바꿀 수 있다.
총 계산해야하는 배열은 V개이다. 따라서 총 시간 복잡도는 $O(VE)$가 된다. 다익스트라 알고리즘의 시간 복잡도 $O(E \log E) = O(E \log V)$임과 비교하면 훨씬 오래 걸리므로, 음의 가중치가 있는 상황이 아니라면 그냥 다익스트라로 푸는 것이 좋다.

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

public class BOJ11657 {
    final int INF = 5_000_001;
    int n;
    Bus[] bus;

    static class Bus {
        int start, end, cost;

        Bus(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        bus = new Bus[m];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            bus[i] = new Bus(start, end, Integer.parseInt(st.nextToken()));
        }
    }

    long[] BellmanFord() {
        long[] minTime = new long[n];
        for (int i = 1; i < n; i++)
            minTime[i] = INF;
        for (int i = 0; i < n; i++) {
            for (Bus b : bus) {
                if (minTime[b.start] != INF && minTime[b.start] + b.cost < minTime[b.end]) {
                    minTime[b.end] = minTime[b.start] + b.cost;
                    if (i == n - 1) return new long[]{-1};
                }
            }
        }
        for (int i = 0; i < n; i++)
            if (minTime[i] == INF) minTime[i] = -1;
        return Arrays.copyOfRange(minTime, 1, minTime.length);
    }

    void solution() throws IOException {
        input();
        StringBuilder sb = new StringBuilder();
        for (long i : BellmanFord()) {
            sb.append(i).append('\n');
        }
        System.out.println(sb);
    }

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