[백준 1865] 웜홀

 

 그래프 이론 문제다. 그래프 이론이나 탐색 문제는 내가 좋아하는 유형이라서 재밌게 풀었다. 웜홀은 비용이 음수인 간선으로 생각할 수 있고, 다시 출발지로 돌아왔을 때 비용 총합이 음수가 되는 경우라면 그래프 내에 음수 사이클이 존재할 때임을 쉽게 짐작할 수 있다.

 따라서 그래프 내의 음수 사이클을 쉽게 찾아낼 수 있는 벨만-포드 알고리즘을 채택해서 문제를 해결했다. 간선 정보는 정점의 개수가 작고, 경로가 중복되는 간선을 쉽게 처리하기 위해서 인접 행렬을 이용해 저장했다. 그리고 문제에서 연결 그래프임을 보장하고 있지 않으므로 모든 정점을 시작점으로 해봐야 하는데, 그렇게 되면 정점의 수와 연결 상태에 따라 시간 초과가 날 우려가 있다.

 나는 이를 막기 위해서, 각 정점별 벨만-포드 알고리즘 과정에서 한 번이라도 탐색된 노드에 대해서는 벨만-포드 알고리즘을 진행하지 않았다. 탐색되었다는 것은 그래프 내에 속해 있었다는 것을 의미하고, 벨만-포드 알고리즘은 특정 그래프 내의 음수 사이클을 판별할 수 있으므로, 이미 탐색된 정점을 시작점으로 다시 탐색하는 것은 불필요하다.

 

 적절한 알고리즘을 알고 있다면, 금방 풀 수 있는 문제였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define INF 987654321

using namespace std;

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

    int tc, n, m, w, s, e, t;

    cin >> tc;

    for(int i=0; i<tc; i++) {
        cin >> n >> m >> w;
        vector<vector<int> > edgeMatrix(n+1, vector<int>(n+1, INF)); //cost matrix

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

            edgeMatrix[s][e] = min(edgeMatrix[s][e], t);
            edgeMatrix[e][s] = min(edgeMatrix[e][s], t);
        }

        for(int j=0; j<w; j++) {
            cin >> s >> e >> t;

            edgeMatrix[s][e] = min(edgeMatrix[s][e], -t);
        }

        bool hasNegativeCycle = false;
        vector<bool> isDirty(n+1, false);
        //시작점 특정x, 모든 vertex 확인
        for(int j=1; j<=n; j++) {
            //BellmanFord
            if(isDirty[j]) continue;

            vector<int> dist(n+1, INF);
            dist[j] = 0;
            queue<int>* q = new queue<int>(); //갱신 vertex
            q->push(j);

            for(int k=0; k<n; k++) {
                queue<int>* newQ = new queue<int>();
                while(!q->empty()) {
                    int cur = q->front();
                    q->pop();

                    isDirty[cur] = true;

                    for(int l=1; l<=n; l++) {
                        if(edgeMatrix[cur][l]!=INF && dist[cur]+edgeMatrix[cur][l]<dist[l]) {
                            dist[l] = dist[cur]+edgeMatrix[cur][l];
                            newQ->push(l);  
                        }
                    }
                }

                delete q;
                q = newQ;
            }

            //negative cycle 확인
            if(!q->empty()) {
                hasNegativeCycle = true;
                break;
            }
        }

        cout << (hasNegativeCycle ? "YES" : "NO") << "\n";
    }
}