[C++] 11657 - 타임머신 (골드4)

1. 문제 설명

11657번: 타임머신

 

---

2. 아이디어

다익스트라 알고리즘인 줄 알았는데 타임머신을 쓰면 음의 가중치가 더해진다.

최적의 해를 찾기 위해서는 비용이 적게 드는 간선을 골라야 하는데 음의 가중치가 있으면 '되돌아간다'의 개념이 아니라 '음의 비용'으로 이동하게 되기 때문에 최적의 해를 찾을 수 없게 된다.

이 경우엔 다른 알고리즘이 필요할 것 같아서 찾아보니 역시나 벨만 포드 알고리즘이란 걸 써야 한다.

 

다익스트라처럼 하나의 정점에서 다른 정점으로 가는 최단거리를 찾지만, 음의 가중치가 있어도 계산이 가능하다.

다만, 고려해야할 경우가 많아지고 로직 자체가 바뀌면서 시간 복잡도가 O(ElogV)에서 O(EV)로 느려진다.

 

벨만 포드 알고리즘의 시작은 출발 노드를 설정하고 최단 거리 테이블을 초기화하는 것은 다익스트라와 같다.

그리고 다음의 과정을 n-1번만큼 반복해야 한다.

1.  모든 간선 E개를 하나씩 확인한다.
2.  각 간선을 이용하여 다음 테이블로 가는 최단 거리 테이블을 갱신한다.

만약 현재 정점의 최단 거리 테이블 정보가 INF라면 2번 작업은 수행하지 않고 continue시킨다.

그리고 문제 조건에 '시간을 무한히 오래 돌릴 수 있다면...'은 음의 간선 순환의 존재 여부를 묻는 것이다.

 

음의 간선 순환

음의 간선 순환이란 위의 경우처럼 무한대의 최단 거리 테이블이 생성되는 경우를 말한다.

사실, 이걸 확인하는 방법은 굉장히 간단하다. 위에서 이미 갱신이 끝났어야 할 최단거리 테이블이

똑같은 반복문을 다시 돌렸을 때, 또 최단거리 테이블이 갱신이 된다면 음의 간선 순환이 존재하는 것이다.

 

여기서 예외처리가 발생하지 않는다면 갱신된 최단 거리 테이블을 조건에 맞게 출력시키면 된다.

 

---

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

#define MAX 501
#define INF 2147483647

using namespace std;

vector<tuple<int, int, int>> graph;
vector<long long> Dist(MAX, INF);

void bellman_ford(int n) {
    Dist[1] = 0;
    for (int i = 1; i <= n-1; i++) {
        for (auto j: graph) {
            int u, v, w;
            u = get<0>(j); v = get<1>(j); w = get<2>(j);

            if (Dist[u] == INF) continue;
            if (Dist[v] > Dist[u] + w) Dist[v] = Dist[u] + w;
        }
    }

    for (auto i: graph) {
        for (auto j: graph) {
            int u, v, w;
            u = get<0>(j); v = get<1>(j); w = get<2>(j);

            if (Dist[u] == INF) continue;
            if (Dist[v] > Dist[u] + w) {
                cout << -1 << "\n";
                return;
            }
        }
    }

    for (int i=2; i <= n; i++) {
        if (Dist[i] == INF) cout << -1 << "\n";
        else cout << Dist[i] << "\n";
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m; cin >> n >> m;

    for (int i=0; i<m; i++) {
        int u,v,w; cin >> u >> v >> w;
        graph.push_back({u, v, w});
    }

    bellman_ford(n);

    return 0;
}