[백준(BOJ)] 웜홀(1865번)_C++

일반적인 최단경로를 구하는 문제들과 다르게 이 문제는 제자리로 돌아왔을 때 시간이 오히려 감소해있는 경우를 구하는 문제다.

시간이 감소해있다는 것은 최단경로를 구할 때 끊임없이 경로가 갱신된다는 의미고, 즉 이는 음수 사이클이 존재한다는 의미다.

따라서 문제에서 주어진 그래프에 음수 사이클이 존재하는지 확인하면 된다.

 

음수 사이클이 존재 하는지 판단하기 위해서는 다익스트라가 아닌 벨만-포드 알고리즘을 통해 해결할 수 있다.

알고리즘 자체는 이해하는데 꽤 어려울 수 있다. 특히 모든 간선에 대해 왜 n-1번을 검사해야하는지 헷갈릴 수 있다.

(내가 그랬다...)

 

이는 사실 직접 그래프를 가지고, 각 노드의 최단 경로 값을 계산해보면 이해하기 수월하다.

간단하게 설명하자면 벨만-포드 알고리즘에서는 1번 노드로부터 나머지 노드까지의 거리를 무한대로 설정하고 시작한다.

(굳이 1번 노드가 아니어도 됨)

이 때문에 모든 간선에 대해 한 번 검사하여 경로값을 갱신하게 되면 1번 노드에 직접 연결된 노드들의 경로값만 갱신되게 된다.

그럼 여기서 한 번 더 검사하게 되면?? 1번 노드에서 2개의 간선을 지난 노드들의 경로값이 갱신된다.

 

이제 슬슬 감이 잡히기 시작하죠?

모든 경로에 대해 k번 검사하면 1번 노드에서 k개의 간선을 지난 노드들의 경로값이 갱신되는 것이다.

 

자 그럼 노드의 개수가 n이라고 가정하면 1번 노드에서 가장 멀리 떨어진 노드는 최대 n-1개의 간선을 거쳐야 한다.

그럼 모든 간선에 대해 n-1번 검사하면 모든 노드에 대해 경로값이 갱신된다.

그런데!!! 만일 음수 사이클이 존재한다면 어떻게 될까?

 

우선 음수 사이클이 존재하지 않는다고 가정을 해보자.

각 노드들의 경로값들이 더이상 갱신되지 않을 것이다. 더 짧은 경로가 없기 때문이다.

 

그럼 음수 사이클이 존재하면 더 짧은 경로가 존재하는 것이므로 또 다시 갱신될 것이다.

즉, n-1보다 더 많이 갱신이 가능하다는 것이다. (사실은 무한정으로 갱신이 되는 것이다.)

 

이러한 이유때문에 모든 간선에 대해 n-1번 검사를 진행하는 것이고,

이후에 한 번 더 갱신되는지에 따라 음수 사이클이 존재하는지 알 수 있다.

 

 

#include <iostream>
#include <vector>
#define INF 2e9

using namespace std;

struct edge{
    int s;
    int e;
    int t;
};

int tc, n, m, w;
int cost[501];

bool bellman_ford(vector<edge> v){
    cost[1] = 0;

    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < v.size(); j++){
            int cur = v[j].s;
            int next = v[j].e;
            int ncost = v[j].t;

            if (cost[cur] + ncost < cost[next])
                cost[next] = cost[cur] + ncost;
        }
    }

    for(int i = 0; i < v.size(); i++){
        int cur = v[i].s;
        int next = v[i].e;
        int ncost = v[i].t;

        if (cost[cur] + ncost < cost[next])
            return true;
    }

    return false;
}

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

    //input
    cin >> tc;
    while (tc--){
        cin >> n >> m >> w;

        int s, e, t;
        vector<edge> v;

        for(int i = 0; i < m; i++){
            cin >> s >> e >> t;

            v.push_back({s, e, t});
            v.push_back({e, s, t});
        }
        for(int i = 0; i < w; i++){
            cin >> s >> e >> t;

            v.push_back({s, e, -t});
        }
        for(int i = 0; i < 501; i++)
            cost[i] = INF;

        //bellman ford algorithm and output
        if (bellman_ford(v) == true)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}