[백준] 1865 : 웜홀, 벨만-포드, 최단 경로 알고리즘 비교

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

1865번: 웜홀

 

최단 거리 문제인데, 벨만 포드를 변형하여 푸는 그래프 문제이다.

 

맞왜틀(맞았는데 왜 틀렸을까) 부분이 많은 문제이기도 하다.

 

벨만 포드

벨만 포드 알고리즘은 음의 가중치를 포함하는 그래프에서, 특정 출발점에서 모든 정점까지의 최단 경로를 구할 때 사용한다.

 

최단 경로 알고리즘 비교

BFS

- 간선의 가중치가 모두 동일할때 하나의 출발점으로부터 각 정점까지의 최단 경로를 찾을 수 있다.

(DFS의 경우 끝 점에 도달할때를 기준으로 하므로 최단 경로를 구하는 것과 관련이 없다.)

 

다익스트라 알고리즘

- 양의 가중치만 있는 그래프에서 사용한다. (가중치가 다양한 그래프일때, 최단 거리를 가장 빠르게 구할 수 있는 알고리즘이다.)

- 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 구할 수 있다.

- 시간복잡도 : O(V+ElogV)

 

벨만-포드 알고리즘

- 음의 가중치를 포함하는 그래프에서 사용한다. (음의 사이클을 감지할 수 있다.)

- 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 구할 수 있다.

- 시간복잡도 : O(VE) : V는 정점의 수, E는 간선의 수

📌 다익스트라보다는 느리지만, 뒤에 나올 플로이드-워셜보다는 빠르다.

 

플로이드-워셜 알고리즘

- 모든 정점 쌍 사이의 최단 경로를 찾을 때 사용한다.

- 음의 가중치를 포함한 그래프에서도 사용가능하다. (음의 사이클을 감지할 수 있다.)

- 시간복잡도 : O(V^3)

 

=> 위 문제에서는 음의 사이클을 판단해야하므로 벨만-포드, 플로이드-워셜 알고리즘을 사용할 수 있다.

 

풀이 방법

1. 벨만-포드 알고리즘 이용

음의 사이클이 존재하는지 구하는 로직 자체는 벨만-포드가 플로이드-워셜보다 간단하다.

벨만-포드는 최단 거리 테이블을 한번 더 갱신하여, 갱신이 되면 음의 사이클이 있음을 확인할 수 있고,

플로이드-워셜은 자기 자신으로의 최단거리가 음수일때 음의 사이클이 있음을 확인할 수 있다.(정점 수만큼 순회해야한다.)

 

맞왜틀이 많이 발생하는 이유

위 문제가 맞왜틀이 많이 발생하는 이유는 주어진 그래프가 연결 그래프가 아니라는 조건을 주지 않았기 때문이다.

즉 시작점을 하나로만 고려했을 경우, 시작점에서 도달할 수 없는 떨어진 그래프에서 음의 사이클이 발생할 수 있으므로 답을 구할 수 없다.

즉 모든 시작점을 고려해야한다.

 

- 이 경우 벨만-포드를 이용하면 모든 시작점만큼 반복하여 벨만-포드를 수행해야한다.

   시간복잡도 : V * O(VE) = O(V^2E) = O(500*500*2700) = 675,000,000 (6억 7천 5백만 연산)

 

- 플로이드-워셜을 수행할 경우 시간복잡도는 더 낮다.

   시간복잡도 : O(V^3) = 125,000,000 (1억 2천 5백만 연산)

 

문제의 종류는 벨만-포드인데 .. 플로이드-워셜이 더 올바른 알고리즘 같다..

우선 벨만-포드 알고리즘을 이용해서 음의 사이클이 있음을 확인해보기로 했다.

(문제 종류가 벨만-포드였기 때문이다. 실제로는 플로이드-워셜 먼저 해보는게 맞다!..)

 

시간초과난 벨만-포드 코드

#include <bits/stdc++.h>
#define INF 1e9
using namespace std; 
int tc, n, m, w, s, e, t;
vector<pair<int, pair<int, int>>> mp;
int d[504];

bool bellmanFord(int start){
    d[start]=0;
    for(int i=1;i<=n;i++){ //n-1번 수행 + 1번(음의 사이클 확인)
        // 모든 간선에 대해 수행
        for(auto &e:mp){
            int from = e.first;
            int to = e.second.first;
            int cost = e.second.second;
            if(d[from] == INF) continue; // start와 이어지지 않은 점이면 무시
            if (d[to] > d[from]+cost){
                d[to] = d[from]+cost;
                if (i==n) return true; // 마지막 반복문에서도 최단거리 테이블 갱신시 음의 사이클 존재
            }
        }
    }
    return false;
}

int main(){
    //1. 입력하기
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cin >> tc;
    while (tc--){
        mp.clear();
        cin >> n >> m >> w;
        for (int i=0;i<m;i++){ // 도로의 개수
            cin >> s >> e >> t;
            mp.push_back({s, {e, t}});
            mp.push_back({e, {s, t}});
        }
        for (int i=0;i<w;i++){ // 웜홀의 개수
            cin >> s >> e >> t;
            mp.push_back({s, {e, t*(-1)}});
        }
        //2. 초기화
        fill(d, d+504, INF);
        //3. 벨만 포드 알고리즘 수행
        bool negativeCycle = false;
        for (int i=1;i<=n;i++){ // 모든 시작점에 대해 => 시간 초과
            negativeCycle = bellmanFord(i);
            // 4. 정답 출력
            if (negativeCycle){
                break;
            } 
        }
        cout << ((negativeCycle==true) ? "YES" : "NO") << "\n";
    }
    
}

당연히 시간초과가 난다. 

 

 

벨만-포드는 최단거리를 구하는 알고리즘이다. 하지만 위 문제에서는 음의 사이클 여부만 확인하면 된다.

그리고 모든 정점에 대해 확인해야한다.

즉, 벨만-포드 알고리즘을 변형해서 문제를 해결해야한다.

 

벨만포드 코드에서 바꿀 지점

- 시작점 개념을 지운다.

기존 벨만-포드 알고리즘은 시작점으로부터 도달하지 못하는 점은 무시했다. (if(d[from] == INF) continue;)

시작점과 관계없이 모든 정점을 대상으로 알고리즘을 수행한다.

 

- 최단 거리 배열을 0으로 초기화한다.

최단 거리 배열(d)을 0으로 초기화 시켜 모든 간선에 대해 최단 거리 배열이 업데이트 되도록 수정한다.

 

=> 이렇게 변형할 경우에 최단 거리 배열은 실제 최단 거리를 나타내는 것이 아닌, 음의 사이클 여부만을 정확히 나타낸다.

 

(음의 사이클이 없다면, 모든 정점을 동시에 출발점으로 고려할때 정점으로 가는 경로 중 최소 비용을 나타내며,

음의 사이클이 있을 경우에는 음의 사이클 여부만을 나타낸다.)

 

변형된 벨만-포드 코드 (맞음)

#include <bits/stdc++.h>
using namespace std; 
int tc, n, m, w, s, e, t;
vector<pair<int, pair<int, int>>> mp;
int d[504];

bool bellmanFord(){
	// 바뀐 부분1 : 시작점 없앰
    for(int i=1;i<=n;i++){ 
        for(auto &e:mp){
            int from = e.first;
            int to = e.second.first;
            int cost = e.second.second;
            // 바뀐 부분2 : from과 시작점이 연결되어있는지 확인 안함
            if (d[to] > d[from]+cost){
                d[to] = d[from]+cost;
                if (i==n) return true; // 음수 사이클 발생
            }
        }
    }
    return false;
}

int main(){
    //1. 입력하기
    cin >> tc;
    while (tc--){
        cin >> n >> m >> w;
        for (int i=0;i<m;i++){ // 도로의 개수
            cin >> s >> e >> t;
            mp.push_back({s, {e, t}});
            mp.push_back({e, {s, t}});
        }
        for (int i=0;i<w;i++){ // 웜홀의 개수
            cin >> s >> e >> t;
            mp.push_back({s, {e, t*(-1)}});
        }
        //2. 벨만 포드 알고리즘 수행 & 정답 출력
        if (bellmanFord()){
            cout << "YES\n";
        }
        else cout << "NO\n";
        // 3. 초기화
        fill(d, d+504, 0);
        mp.clear();
    }
    
}

위 코드의 시간복잡도는 O(V * E) = O(n * (m+w)) 이다.

테스트 케이스마다 반복한다면 O(tn * (m+w))이다.

 

결국 플로이드-워셜보다 훨씬 빠르다!

5시간을 소요하여 문제를 보고 풀고, 질문 게시판 들여다보고, chatgpt 물어보고 여기저기 떠돌아다닌 보람이 있다.

 

2. 플로이드-워셜 알고리즘 이용

플로이드-워셜을 이용해서도 풀 수 있다.

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int tc, n, m, w, s, e, t;
int dist[504][504];

void floydWarshall() {
    for (int k = 1; k <= n; k++) { 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) { // 자기 자신의 점도 포함
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

int main() {
	//1. 입력받기
    cin >> tc;
    while (tc--) {
        cin >> n >> m >> w;

        // 초기화
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = (i == j) ? 0 : INF;
            }
        }

        // 도로와 웜홀 정보 입력
        for (int i = 0; i < m; i++) {
            cin >> s >> e >> t;
            dist[s][e] = min(dist[s][e], t);
            dist[e][s] = min(dist[e][s], t);
        }
        for (int i = 0; i < w; i++) {
            cin >> s >> e >> t;
            dist[s][e] = min(dist[s][e], -t);
        }

        // 2. 플로이드-워셜 알고리즘 실행
        floydWarshall();

        // 3. 음의 사이클 검출
        bool negativeCycle = false;
        for (int i = 1; i <= n; i++) {
            if (dist[i][i] < 0) {
                negativeCycle = true;
                break;
            }
        }
		//4. 정답 출력
        if (negativeCycle) {
            cout << "YES" << "\n";
        } else {
            cout << "NO" << "\n";
        }
    }
    return 0;
}

 

시간 복잡도가 더 크지만 좀 더 깔끔한 코드이다.