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

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

• 예제 출력 1

4
3

• 예제 입력 2

3 4
1 2 4
1 3 3
2 3 -4
3 1 -2

• 예제 출력 2

-1

• 예제 입력 3

3 2
1 2 4
1 2 3

• 예제 출력 3

3
-1

Solution

#include <iostream>
#include <vector>
#define MAX 501
#define INF 987654321
using namespace std;
int N, M;
vector<pair<int, int>> vec[MAX];
long long DISTANCE[MAX];

bool bellman_ford(int start){
    DISTANCE[start] = 0;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            for (int k = 0; k < vec[j].size(); k++){
                int next = vec[j][k].first;
                int cost = vec[j][k].second;
                if (DISTANCE[j] != INF && DISTANCE[next] > DISTANCE[j] + cost){
                    DISTANCE[next] = DISTANCE[j] + cost;
                    if (i == N) return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) DISTANCE[i] = INF;
    for (int i = 0; i < M; i++){
        int A, B, C;
        cin >> A >> B >> C;
        vec[A].push_back({B, C});
    }
    bool negative_cycle = bellman_ford(1);
    if (negative_cycle) cout << "-1\n";
    else{
        for (int i = 2; i <= N; i++){
            if (DISTANCE[i] == INF) cout << "-1\n";
            else cout << DISTANCE[i] << '\n';
        }
    }
}

Bellman Ford 알고리즘 대표문제다.
Dijkstra 와는 다르게 간선에 비용이 음수인 경우도 처리할 수 있다는 것. 비용이 음수인 경우가 있지 않는 한 굳이 이 알고리즘을 쓸 필요는 없기는 하다. 아무래도 시간 복잡도 면에서 Dijkstra가 유리하기도 하니까(우선순위 큐 사용).
Bellman Ford 알고리즘은 다음과 같다.

1. 출발 노드를 설정
2. 최단 거리 테이블 초기화
3. 모든 간선E개를 하나씩 확인 후
4. 각 간선을 거쳐 다른 노드로 가는 비용을 계산해서 최단거리 테이블을 갱신
5. 3과 4를 정점 -1 번 반복, 만약 음수 간선 Cycle이 있는 지 확인하고 싶다면 한번 더 반복. 최단 거리 테이블이 갱신된다면 Cycle이 존재하는 것이다.

Negative Cycle이라고도 부르는 음수 간선 Cycle이 존재한다면 해당 Cycle을 돌면 돌 수록 최단 거리 테이블이 작게 갱신되므로 최단 거리를 구하는 게 의미가 없어진다.
즉 이러한 Cycle이 존재한다면 Bellman Ford 알고리즘은 사용할 수 없다.
이번 문제에서는 음수 비용은 곧, 시간을 되돌리는 경우라고 할 수 있다. 무한히 시간을 되돌리는, 즉 Negative Cycle이 존재하면 -1를 출력하라고 했으므로 Bellman Ford 알고리즘을 활용할 수 있다.

cin >> N >> M;
for (int i = 1; i <= N; i++) DISTANCE[i] = INF;
for (int i = 0; i < M; i++){
    int A, B, C;
    cin >> A >> B >> C;
    vec[A].push_back({B, C});
}

Dijkstra를 활용할때와 마찬가지로 데이터를 입력받는다.

bool bellman_ford(int start){
    DISTANCE[start] = 0;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            for (int k = 0; k < vec[j].size(); k++){
                int next = vec[j][k].first;
                int cost = vec[j][k].second;
                if (DISTANCE[j] != INF && DISTANCE[next] > DISTANCE[j] + cost){
                    DISTANCE[next] = DISTANCE[j] + cost;
                    if (i == N) return true;
                }
            }
        }
    }
    return false;
}

Dijkstra를 구현 할 때에 비하면 상당히 코드가 터프하다. 플로이드 와샬보다는 좀 낫겠지만...

for (int j = 1; j <= N; j++){
    for (int k = 0; k < vec[j].size(); k++){
        int next = vec[j][k].first;
        int cost = vec[j][k].second;
        if (DISTANCE[j] != INF && DISTANCE[next] > DISTANCE[j] + cost){
           DISTANCE[next] = DISTANCE[j] + cost;
           if (i == N) return true;
     	}
    }
}

가장 끝의 for문은 마지막으로 Negative Cycle을 체크하는 용도로 N번 반복된다. 원래는 N-1 번 for문이 작동한다.
1번 노드부터 하나하나 탐색을 시작한다. 간단하다. j번 노드에 연결 된 k번 째 노드의 데이터를 통해 j로 가는 경로가 있으며, j를 통해 비용을 지불하고 가는 것이 더 빠르다면 해당 노드의 Distance를 갱신하는 식이다. 만약 N번째 반복에서 이 과정이 실행되었다면, Negative Cycle이 있다는 의미이므로 return true를 한다.

bool negative_cycle = bellman_ford(1);
if (negative_cycle) cout << "-1\n";
else{
    for (int i = 2; i <= N; i++){
         if (DISTANCE[i] == INF) cout << "-1\n";
         else cout << DISTANCE[i] << '\n';
    }
}

negative cycle bool 형 데이터가 true면 영원히 타임머신을 타야하므로 -1 출력, 그 외에는 INF가 아닌이상 각자 Distance가 갱신되었을테니 그대로 출력한다.

Dijkstra, Bellman ford는 반드시 숙지해야하는 주요 알고리즘이므로 이해가 안되면 외워서라도 써먹자.