[boj] 백준 1865 웜홀 (c++) - 벨만 포드 알고리즘

[문제]

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

1865번: 웜홀

 

[풀이]

벨만-포드 알고리즘에서 n번째 탐색을 진행하였을 때 값이 변하는 부분이 있다면 음의 사이클이 존재한다는 것을 파악할 수 있다. 

 

다만, 기존의 벨만-포드 알고리즘 구현과 차이를 두어야 하는 부분이 있어 짚어보았다.

- INF 비교하는 부분을 빼야 한다. 기존의 벨만 포드 구현 시에는 if (dist[s] == INF) continue 문을 통해 한 번 계산된 적이 있는 시작 정점에 대해서만 갱신을 진행하였다. 이는 단절되어 있는 정점에 의해 최단 경로가 갱신되는 것을 방지하기 위해서였다. 하지만 이 문제에서는 음의 사이클 존재여부만 알면 된다. 만약 단절된 정점들끼리 사이클을 형성하였는데 INF 비교 문을 통해 지나친다면 사이클 형성 여부를 판단할 수 없게 되는 것이다! (모든 정점을 출발점으로 조사하여 사이클 생성 여부를 판단할수도 있으나 해당 문제에서는 시간초과가 뜬다고 한다.)

- 이 문제에서는 거리를 구하는 것이 아닌 사이클 유무만 판단하는 것이 핵심이므로 시작 정점의 거리를 0으로 초기화해주지 않아도 된다. dist[s] = 0 코드를 쓰지 않아도 음의 사이클 유무 판단에는 아무 상관이 없다. 애초에 임의의 시작점을 0으로 해준 것 역시 한 번 계산된 적이 있는 시작 정점에 대해서 갱신이 진행되기 때문이었다. 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define INF 987654321

using namespace std;

int t;
int dist[501];

bool bellman_ford(int n, vector<pair<int, pair<int ,int >>> edge){
    //dist[1] = 0;
    for(int i=0; i<n-1; i++){
        for(int j=0; j<edge.size(); j++){
            int cost = edge[j].first;
            int s = edge[j].second.first;
            int e = edge[j].second.second;

            if(dist[e] > dist[s] + cost)
                dist[e] = dist[s] + cost;
        }
    }

    for(int j=0; j<edge.size(); j++){
        int cost = edge[j].first;
        int s = edge[j].second.first;
        int e = edge[j].second.second;

        if(dist[e] > dist[s] + cost){
            return true; //음의 사이클이 생김
        }
    }
    return false;
}

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

    cin >> t;
    while(t--){
        int n, m, w;
        cin >> n >> m >> w;
        vector<pair<int, pair<int, int>>> edge;
        
        for(int i=0; i<m; i++){ //도로 정보, 무방향
            int s, e, t;
            cin >> s >> e >> t;
            edge.push_back({t, {s,e}});
            edge.push_back({t, {e, s}});
        }
        for(int i=0; i<w; i++){ //웜홀 정보
            int s, e, t;
            cin >> s >> e >> t;
            edge.push_back({-t, {s, e}});
        }

        fill(dist, dist+501, INF);

        if(bellman_ford(n, edge))
            cout << "YES\n";
        else cout << "NO\n";

    }
}