[백준][C++] 1865번: 웜홀 <196>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

워프를 통해서 시간을 되돌릴 수 있다는 말을 보자마자 생각난것은 음의 가중치를 갖는 간선 이였다.

이 문제는 음의 가충치를 갖는 사이클이 있는지 확인해야 하는 문제이다.

 

따라서 벨만 포드 알고리즘이 적합하다. 벨만포드 알고리즘의 sudo 코드는 다음과 같다.

// 입력: 가중치 그래프 G
// 출력: dist 배열, dist[u]는 v에서 u까지의 최단거리
BellmanFord(G, v) {

    for each u ∈ V
    	dist[u] <- INF;
        
    dist[r] <- 0; // 시작지점은 0으로 초기화
    for i <- 1 to |V|-1 // 총 정점의 수 - 1 만큼 반복
        for each (u, v) ∈ E
            f dist[u] + weight[u][v] < dist[v]
                then dist[v] <- dist[u] + weight[u][v];
}

for 루프가 n-1번 반복된다.

i번째 루프가 끝나면 최대 i개의 간선을 사용해서 도달할 수 있는 최단 경로를 계산하게 된다.

 

for루프를 돌기 전에는 i=0이기 때문에 하나의 간선도 사용하지 않고 도달할 수 있는 최단 경로만 계산되기 때문에 시작지점이 0으로 초기화 되는것 이다.

이후 for 루프가 한번 돌면 i=1인 상태이기 때문에, 단 하나의 간선을 사용해서 r부터 이을 수 있는 최단 경로가 계산된다.

즉, r로부터 바로 연결된 정점들의 최단 거리에 변동이 생긴다.

 

따라서 n-1번째 루프가 끝나면 n-1 개의 간선을통해 도달할 수 있는 최단경로가 계산되었다는 의미이다. 

최대 n-1개의 간선을 사용해서 이를 수 있는 최단경로가 이 그레프에서의 최단 경로이다.

 

문제는 n-1 번째 까지 했을때 최단 경로가 나와야 하는데, 그 이후에 최단 경로가 더 작은값으로 갱신된다면 이는 음의 사이클이 존재한다는 의미이다. 

즉, 백준이가 원래 시작지점으로 원래 시작 시간보다 이른시간에 도달할수가 있다는 의미이다.

 

따라서 음의 사이클 유무를 이후에 판단해주면 된다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 2501
#define INF 10001

int T, N, M, W;
int dist[501];
vector<pair<int, int>> adj[MAX];

bool isHasNegativeCycle(){
    dist[1] = 0;
    for(int i = 1; i <= N-1; i++){
        for(int j = 1; j <= N; j++) {
            for (auto v : adj[j]) { // 매 순서 마다 모든 정점을 확인
                int from = j;
                int to = v.second;
                int cost = v.first;
                if (dist[from] + cost < dist[to]) {
                    dist[to] = dist[from] + cost;
                }
            }
        }
    }

    for(int j = 1; j <= N; j++){ // 음의 정점이 있는지 확인
        for (auto v : adj[j]) { // 매 순서 마다 모든 정점을 확인
            int from = j;
            int to = v.second;
            int cost = v.first;
            if (dist[from] + cost < dist[to]) {
                return true;
            }
        }
    }
    return false;
}

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

    cin >> T;
    for(int i = 0; i < T; i++){
        cin >> N >> M >> W;
        int S, E, T;
        for(int j = 0; j < M; j++){
            cin >> S >> E >> T;
            adj[S].push_back({T, E});
            adj[E].push_back({T, S});
        }
        for(int j = 0; j < W; j++){
            cin >> S >> E >> T;
            adj[S].push_back({-T, E});
        }

        if(isHasNegativeCycle()){
            cout << "YES\n";
        }else{
            cout << "NO\n";
        }

        memset(dist, INF, sizeof(dist));
        for (int i = 1; i <= N; ++i) adj[i].clear();
    }

    return 0;
}