[백준 알고리즘] 11657번: 타임머신

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

문제

문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

출력
만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, …, N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

풀이

정말 역대급으로 힘든 문제였다. 벨만포드 알고리즘을 공부하고 바로 시도해 본 문제였는데도 구현이 잘 안됐다. 가장 어려웠던 부분이 직접 그래프를 표현해야되는 부분이었는데, 구조체를 통해서 출발점, 도착점, 간선 가중치를 표현하는 방법을 선택했다. 벨만포드 알고리즘은 크게 세 부분으로 나누어진다.

1. 초기화 : 모든 정점의 최단거리를 최대치로 표현해주어야 한다. 처음에는 문제의 조건에서 c의 최대 값이 10000 이길래 10001을 초기값으로 잡았는데, 각 정점을 업데이트 하는 과정에서 정점의 갯수가 최대 500개 이므로, 값은 최대 5000000 이상으로 잡힐 수 있어서 더 큰 값으로 잡아주어야 했다.
2. Relaxation : 벨만포드 알고리즘의 핵심이고 머리로는 잘 이해가 되지만 실제로 구현하려고할 때, 제일 막히는 부분이었다. 일단 모든 정점에 대해서 relaxation을 진행해주어야 하는데, 우리가 초기값으로 설정하는 최단거리는 사실상 무한대가 아니기 때문에 다른 노드와 연결되어 있지 않은 정점에 대한 계산을 할때, 무한대를 실제 거리처럼 계산하는 오류가 있었다. 예를 들어, 1번 정점이 2번 정점과 연결되어 있지 않다면, 2번정점을 검사할 때, 그 정점의 최단거리가 5000000으로 설정이 될텐데, 여기에 다른 정점과 이어지는 간선 가중치를 더하거나 빼게되면 최대치와 다른 값이 나오게 되므로, 어떤 경우에는 4999999와 같은 값들이 최단거리로 설정됐다. 따라서 우리가 설정한 최대치가 노드의 relaxation을 시작하는 시점에 해당 노드의 최단거리로 설정되어 있다면, 시작점 노드와 연결되어 있지 않은 노드이기 때문에, 그 노드의 최단거리는 업데이트하지 않고 나중에 -1로 표시하게 해야했다.
3. 음수 사이클 확인: 음수 사이클을 확인하는 과정은 2번 과정을 정확히 한번 더 수행하는 대신에, 새로 갱신이 가능한 최단거리가 나타난다면 곧바로 해결 불가능한 문제라고 결정하고 -1을 출력한 후 종료되게 한다. 나는 Relaxation 코드를 한번 더 사용했는데, 다른 사람들의 코드를 보니 relaxation 단계의 반복횟수를 한번 더 늘리고 마지막 반복에서 갱신값이 생기면 프로그램을 종료시키게 했다. 이게 더 깔끔한 방법인 것 같다.

알고리즘을 아는 것 은 이론을 알고 그 이론을 주어진 문제에 적용하는 것이다. 정말 공부를 하면서 겉핥기 식으로 구조와 원리를 이해했다고 자만하지 말자. 구현해보고 문제를 풀어보자. 그리고 나의 무지함과 부족함을 경험하자.

코드

#include <cstdio>
#include <vector>
#include <climits>

#define INF 7000000
using namespace std;

typedef struct{
    int here;
    int there;
    int cost;
}edge;

long long d [501] = {0,};
vector<edge> edges;

int main (){
    int v, e;
    scanf("%d %d", &v, &e);
    for (int i = 2 ; i <= v ; i++) d[i] = INF;
    for (int i = 0 ; i < e ; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back({a, b, c});
    }

    /* 모든 정점에 대한 relaxation */
     for (int i = 1 ; i <= v-1 ; i++){
        for (int j = 0 ; j < e ; j++){
            int from = edges[j].here;
            int to = edges[j].there;
            int w = edges[j].cost;

            if (d[from] == INF) continue; // 출발점 노드가 다른 이전에 다른 노드와 이어져있지 않은 경우
            if (d[to] > d[from] + w) d[to] = d[from] + w;
        }
    }

    /* 음수 사이클 체크  */
    for (int i = 1 ; i <= v-1 ; i++){
        for (int j = 0 ; j < e ; j++){
            int from = edges[j].here;
            int to = edges[j].there;
            int w = edges[j].cost;

            if (d[from] == INF) continue;

            if (d[to] > d[from] + w) {
                printf("-1\n");
                return 0;
            }
        }
    }

    for (int i = 2 ; i <= v ; i++){
        d[i]==INF ? printf("-1\n") : printf("%lld\n", d[i]);
    }

}