[백준] 11657 타임머신 - 자바, 출력초과 해결

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

11657번: 타임머신

문제 풀이

음의 간선이 존재하는 그래프에서 최단 경로를 구하기 위해선 벨만-포드 알고리즘을 적용해야 한다.

그렇다면 왜 음의 간선이 있다면 다익스트라 알고리즘을 적용할 수 없을까?

먼저 다익스트라를 구현하는 방법은 두 가지로 나눌 수 있다.

1. 중첩반복문을 사용하여 방문하지 않은 최소 비용의 간선을 선택하여 최단 경로를 업데이트 -> O(V^2)
2. 우선순위 큐를 사용하여 최소 비용 간선을 선택하는데 더욱 효율적으로 최단 경로 업데이트 -> O(ElogV)

위 이론을 가지고 테스트 케이스 2번을 확인해보자

1번 노드를 살펴보면 초기에 1->1은 당연히 0의 비용이 들 것이다. 하지만 1->2->3->1로 간다면 4-4-2로 총 -2의 비용이 든다. 즉 이 사이클 1->2->3->1을 계속 반복한다면 1의 최단 경로는 음의 무한대로 가진다. 이러한 이유로 다익스트라의 최소 비용 간선을 선택하거나, 우선순위 큐에 최소 비용을 갖는 노드를 삽입하는 과정에서 무한루프가 발생한다.

 

물론 하드 코딩으로 처리는 해줄 수 있을 것 같지만 매우 복잡해보인다. 따라서 벨만-포드 알고리즘을 통해 음의 간선이 존재 하는 그래프에서 최단 경로를 구해야 한다.

 

그럼 벨만 포드는 어떻게 작동하길래 음의 간선 사이클을 탐지하여 최단 경로를 구할까?

이미 최단 경로를 구했는데 최단 경로를 업데이트 하는 로직을 다시 실행시켰더니 값이 더 작은 비용으로 업데이트가 됐다? -> 음의 간선 순환 발생

위 이론을 적용시켜 좀만 더 생각을 해보자. 모든 경로마다 몇 번의 업데이트 로직을 통해 즉, 몇 개의 간선으로 최단 비용이 이루어지는지 체크하기엔 매우 복잡하다. 따라서 모든 경로에 대해 최대 간선을 가질 수 있도록 업데이트 로직을 실행시켜주면 된다.

이해가 안 간다면 간단한 예시를 살펴보자.

노드가 4개가 있다. 몇 개의 간선이 있는진 모르지만 한 노드에서 특정 노드로 이동했을 때 가질 수 있는 최단 거리의 간선은 3개이다. (음의 순환이 없다고 가정)

다음과 같은 그래프가 있을 때 우리는 한 눈에 봤을 때 D로 가는 최소 비용을 구할 수 있지만 우리는 최소 비용을 업데이트 하는 로직을 통하여 한 간선씩 비교하게 된다.

A B 1
B C 2
C D 3

C D 3
B C 2
A B 1

간선이 다음과 같이 A B 부터 순차적으로 주어졌다면 업데이트 로직 1번만으로 D의 최단 경로가 6으로 바로 나올 것이다.

하지만 C D 3 부터 역순으로 나왔다고 생각해보자. 

업데이트 로직 1회 -> d[D] = 3

업데이트 로직 2회 -> d[D] = 5

업데이트 로직 3회 -> d[D] = 6

총 3회에 걸쳐 최단 경로를 구할 수 있다. 

하지만 여기서 업데이트 로직을 다시 수행한다고 해서 d[D]는 변하지 않는다. 

 

따라서 적어도 V-1번의 업데이트 로직을 실행시키고 그 이후에도 만약 최단 경로가 업데이트가 됐다면 음의 순환이 일어났다는 뜻이다.

 

물론 음의 순환은 V-1번을 실행하는 동안에도 일어난다. 계속해서 작은 비용의 값으로 업데이트 될 것이다. 하지만 굳이 처리해줄 필요 없다. 어차피 V-1번 이후의 로직에서 업데이트가 또 일어나기 때문에 여기서 필터링 해주면 된다.

 

출력 초과 해결

추가로 이 문제는 N이 최대 500, M이 최대 6000, C가 최소 -10,000이다. 모든 간선의 비용이 -10,000일 때 최단 경로는 499 * 6000 * -10,000 으로 int의 범위를 훨씬 벗어난다.

따라서 최단 경로를 저장해주는 d[]는 long으로 처리해줘야 한다.
long으로 처리하지 않으면 출력 초과가 발생한다.

코드

package 백준;

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

class Bus {
    int from;
    int to;
    int time;
    public Bus(int from, int to, int time) {
        this.from = from;
        this.to = to;
        this.time = time;
    }
}

public class b11657 {

    static final int INF = 500 * 10_000;
    static int N, M;
    static Bus[] buses;
    static long[] d;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        //init
        d = new long[N + 1];
        Arrays.fill(d, INF);
        buses = new Bus[M + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());

            buses[i] = new Bus(from, to, time);
        }

        // 음의 cycle이 없는 경우
        if (bellmanFord())
            for (int i = 2; i <= N; i++)
                sb.append(d[i] == INF ? "-1\n" : d[i] + "\n");
        // 음의 cycle이 있는 경우
        else
            sb.append("-1");

            System.out.println(sb);

    }
    static boolean bellmanFord () {
        // 시작 정점
        d[1] = 0;

        // V-1번 최소경로 업데이트
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < M; j++) {
                Bus bus = buses[j];
                int from = bus.from;
                int to = bus.to;
                int time = bus.time;

                if (d[from] != INF && d[to] > d[from] + time) {
                    d[to] = d[from] + time;
                }
            }
        }

        // 다시 한번 업데이트
        for (int i = 0; i < M; i++) {
            Bus bus = buses[i];
            int from = bus.from;
            int to = bus.to;
            int time = bus.time;

            // 최소 경로가 다시 업데이트 된다면 음의 간선 사이클 존재
            if (d[from] != INF && d[to] > d[from] + time)
                return false;
        }
        return true;
    }
}