[C++] 백준 1865: 웜홀

문제 이해

- N개의 지점

- 방향이 없는 M개의 도로

- 방향이 존재하는 음의 가중치를 가진 W개의 웜홀

- 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 탐색하라.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 512MB

 

<입력>

TC: 테스트 케이스의 개수 (1 ~ 5)

N: 지점의 수 (1 ~ 500, 10^2)

M: 도로의 개수(1 ~ 2,500, 10^3)

W: 웜홀의 개수(1 ~ 200, 10^2)

 

<출력>

- TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력하라.

 

 

 

문제 풀이

음의 가중치를 가진 최단 경로 탐색이라는 점에서 '벨만-포드 알고리즘' 사용해야 함을 인지했다.

문제에서 원하는 것은 시간이 줄어들면서 출발 위치로 돌아올 수 있는지(음의 사이클이 존재하는 지 탐색하는 것)이었다.

 

 

도로가 방향성이 없으므로 양방향 모두 넣어주었고,

웜홀의 경우 음의 가중치로 넣어주어야 하기에 -1을 곱해주었다.

 

 

처음에는 모든 시작점에 대해서 벨만-포드 알고리즘을 사용했는데

88%쯤 가서 시간 초과가 나왔다.

계산해보니 최악의 경우에는 10^9으로 시간 제한 2초를 넘김을 확인하였다.

 

 

 

 

그렇다면 어떻게 해야할까?

바로 한 정점에서만 벨만-포드 알고리즘을 사용해주는 것이다.

 

그런데, 그렇게하면 웜홀의 방향성 때문에 문제가 되진 않을까???

라고 의문을 품으신다면 벨만-포드 알고리즘에 대해서 잘 숙지하고 있는 것이다!

 

 

 

 

그걸 해결할 답은 바로 아래 코드에 있었다.

if(dist[start] == INF) continue;

 

위의 코드는 벨만-포드 알고리즘에서

한 번도 방문하지 않은 정점에 대해서는 계산하지 않기 위해 사용하는 코드인데,

 

 

 

 

사실 우리는 '최단 경로의 비용을 구하고 싶은 게 아니라 음의 사이클을 확인'하고 싶다.

즉, 방문하지 않은 정점들끼리 음의 사이클을 형성한 것도 알아보고 싶은 것이다.

 

그렇기에 저 코드를 없앰으로써 한 정점에서 벨만-포드 알고리즘을 사용하여도

전체에서 음의 사이클이 존재하는지 않는지 알 수 있는 것이다!!!

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

struct Road{
    int start;
    int end;
    int cost;
};

long long dist[505];

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

    int tc;
    cin>>tc;
    while(tc--){
        int n, m, w;
        cin>>n>>m>>w;

        int s, e, t;
        vector <Road> road;
        for(int i = 0; i < m; i++){
            cin>>s>>e>>t;
            road.push_back({s, e, t});
            road.push_back({e, s, t});
        }
        for(int i = 0; i < w; i++){
            cin>>s>>e>>t;
            road.push_back({s, e, -1 * t});
        }

        for(int i = 1; i <= n; i++) dist[i] = INF;
        dist[1] = 0; //시작점

        bool flag = false;
        int size = road.size();
        for(int t = 1; t <= n; t++){
            for(int i = 0; i < size; i++){
                int start = road[i].start;
                int end = road[i].end;
                int cost = road[i].cost;

                //if(dist[start] == INF) continue; 단순 사이클의 유무만 판단하기에 없앰.

                if(dist[end] > dist[start] + cost){
                    dist[end] = dist[start] + cost;

                    if(t == n){
                        flag = true;
                        break;
                    }
                }
            }
        }

        if(flag) cout<<"YES\n";
        else cout<<"NO\n";
    }
    
    return 0;
}

벨만-포드 알고리즘에서 '음의 사이클'만을 탐색하고 싶을 때 시간 복잡도를 줄이는 방법을 배울 수 있었다!