[알고리즘/C++] - SPFA(Shortest Path Faster Algorithm, 웜홀 - 1865) / 이게 BFS가 아니라 SPFA래

안냐세요
오랜만에 알고리즘으로 돌아왔습니다.
오늘은 알고리즘을 먼저 공부한 게 아니라
문제를 풀다가 새로운 알고리즘을 [발견!]해서 정리를 좀 해보려고 글을 썼다는 큰 차이가 있습니다.
지피티와 함께하는 알고리즘놀이
시작하도록 하겠습니다.
 

---

문제 [웜홀 - 1865]

우선 제가 마주친 문제부터 보겠습니다
https://www.acmicpc.net/problem/1865

 
월드나라의 백준이가 시간여행을 하며 출발한 위치로부터 다시 도착하기까지의 시간이 마이너스인 경우가 있는지를 구하는 내용입니다.
 
예제를 살피겠습니다

예제의 경우 2가지 케이스를 입력하였는데, 먼저 첫번째 예제를 그림으로 살펴보겠습니다.

과거로 돌아갈 수 있는 웜홀은 단방향,
기본 도로는 양방향이기에 이런 그림이 나오는 것을 알 수 있습니다.
 
그럼 이제, 여기서 해야할 일은
1에서 출발했을 때, 1로 다시 돌아오는 최소 경로
2에서 출발했을 때, 2로 다시 돌아오는 최소 경로
3에서 출발했을 때, 3으로 다시 돌아오는 최소 경로
이렇게 세가지의 값을 구하게 됩니다.
 
그리고 여기서, 최소 경로가 음수인 경우에는 과거로 시간을 돌린 것이므로 yes, 아니라면 no를 출력합니다.
 
 

첫번째 시행착오

그래서 고안한 접근 방법은 
1. 루트의 개수만큼 리스트를 만들고, 출발지점을 기준으로 루트를 추가해나감(ex: 2에서 출발하는 경우, 2번째 리스트에 목적지,값을 쌍으로 하여 데이터를 추가함)
2. 도로의 경우 양방향이므로, 출발지와 목적지를 바꿔서 2번 저장
3. 웜홀의 경우 단방향이므로 1번만 저장. 단, 과거로 돌아가므로 음수로 변환
4. 1번부터 n번까지의 출발점을 반복문으로 돌림
4-1. BFS를 통해 출발지와 이어진 길에 대한 리스트를 가져와 경로 이동
4-2. 단, 여기서 방문처리를 하지 않고, 값 비교를 통해 이동을 진행함
5. 최종값이 음수가 나오는 출발점이 존재할 때까지 반복, 끝까지 음수가 나오지 않으면 no출력
 
이러한 방법으로 접근하였습니다.
이 방법은 BFS지만 방문 확인 대신, 최소 비용을 비교하여 경로를 탐색한다는 점에서 조금 다릅니다. 이전에 공부했던 A*나 다익스트라의 개념에서 조금 착안하여 작성하였습니다.
작성된 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <climits>   // INT_MAX, INT_MIN


using namespace std;


int minCost[501] = { 0, };
vector<vector<pair<int, int>>> road;

bool find(int n) {
    queue<int> q;
    q.push(n);
    do {
        int start = q.front();
        q.pop();
        if (start == n && minCost[n] == INT_MAX)
            minCost[n] = 0;
        else if (start == n && minCost[n] < 0)
            break;
        else if (start == n)
            continue;

        for (int i = 0; i < road[start].size(); i++) {
            int end = road[start][i].first;
            int cost = road[start][i].second;
            if (minCost[end] > (long long)cost + minCost[start]) {
                minCost[end] = cost + minCost[start];
                q.push(end);
            }
        }
    } while (!q.empty());
    return(minCost[n] < 0);
}


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

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, m, w;
        int list[200];
        cin >> n >> m >> w;

        //초기화
        road.clear();
        road.resize(n + 1);
        fill(minCost, minCost + 501, INT_MAX);

        //도로 입력
        for (int j = 0; j < m; j++) {
            int s, e, t;
            cin >> s >> e >> t;
            road[s].push_back({ e,t });
            road[e].push_back({ s,t });
        }
        //웜홀 입력
        for (int j = 0; j < w; j++) {
            int s, e, t;
            cin >> s >> e >> t;
            road[s].push_back({ e,-t });
            list[j] = s;
        }
        //최소 거리 찾기
        bool isFind = false;
        for (int j = 0; j < w; j++) {
            if (find(list[j])) {
                isFind = true;
                break;
            }
        }
        string isCan = isFind ? "YES" : "NO";
        cout << isCan << "\n";
    }



    return 0;
}

 
이리저리 헤맸으나 결국에는 정답을 찾을 수 있는 알고리즘을 작성하였습니다.
하지만 시간초과로 실패하고 대체 뭘 해야 시간을 줄일 수 있을까 고민하며 결국엔 지피티니 찬스를 사용하게 되었습니다..ㅠ
정답은 잘 나오는데 자꾸 시간초과야 잉잉
하면서 지피티니에게 달려갔습니다..
 
그런데 이게!!BFS가 아니라고 합니다!!!!!!
엥?????

헐. ㅋ
그럼 이 SPFA는 뭘까요,,
겸사겸사 알아보았습니다..
 

---

SPFA

: Shortest Path Faster Algorithm 의 약자로, 벨만 포드 알고리즘을 개선한 알고리즘. 음수 가중치가 존재하는 그래프에서 음수 사이클을 검사하거나 경로를 탐색할 때, 사용하는 알고리즘이다.

 
장단점

이 SPFA의 경우 구현이 간단하고, 벨만 포드 알고리즘 개선 버전인만큼 일반적으로 벨만 포드 알고리즘보다 효율적이며, 상황에따라서는 기본적으로 경로탐색에 자주 쓰이는 다익스트라 알고리즘보다 빠른 실행 속도를 가지는 경우도 많습니다.
 
하지만, 이 알고리즘 탐색 방법은 최악의 경우 O(VE)의 시간복잡도를 가지고 있기에 위에서 말한 것처럼 반드시 다익스트라보다 빠르다고 보장할 수는 없으며, 최적화가 없다는 단점이 존재합니다.
 
동작원리
기본적인 동작 원리는 위에서 짠 저의 방법과 비슷합니다.
큐를 활용하여 동작하며, 방문 여부 대신 짧은 경로 비교를 통해 갱신 및 진행을 하게 됩니다.
 
1.시작 정점을 큐에 넣고, 시작 정점의 최단 거리를 0으로 초기화
2. 큐에서 정점을 하나 꺼냄
3. 해당 정점에서 나가는 간선을 확인하면서 더 짧은 경로가 발견되면 갱신
4. 갱신된 정점이 아직 큐에 없으면 큐에 추가
5. 큐가 빌 때까지 반복
 
 
간단하게 이 SPFA를 지피티를 통해 대표적인 코드 예시를 받아와보겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to, cost;
};

int n, m; // 정점, 간선 수
vector<vector<Edge>> graph;
vector<int> dist;
vector<bool> inQueue;

bool SPFA(int start) {
    dist.assign(n + 1, INT_MAX);
    inQueue.assign(n + 1, false);
    vector<int> count(n + 1, 0); // 각 정점이 큐에 들어간 횟수 (음수 사이클 판별)

    queue<int> q;
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (auto &e : graph[u]) {
            if (dist[u] != INT_MAX && dist[e.to] > dist[u] + e.cost) {
                dist[e.to] = dist[u] + e.cost;

                if (!inQueue[e.to]) {
                    q.push(e.to);
                    inQueue[e.to] = true;
                    count[e.to]++;

                    // 만약 어떤 정점이 n번 이상 큐에 들어가면 → 음수 사이클 존재
                    if (count[e.to] >= n) return false;
                }
            }
        }
    }
    return true; // 음수 사이클 없음
}

int main() {
    cin >> n >> m;
    graph.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    if (SPFA(1)) {
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INT_MAX) cout << "INF\n";
            else cout << dist[i] << "\n";
        }
    } else {
        cout << "Negative Cycle Detected\n";
    }
}

 
 
그런데 이상한 점이 있습니다..

엥? 최악의 경우 벨만 포드와 같다고?
그렇다면 SPFA를 써도 되는 것 아닌가? 
왜 굳이 벨만 포드를 써야할까???용?

그렇다고 합니다..
 
정리하자면,
평균적으로 SPFA가 빠르긴 하지만, SPFA가 가질 수 있는 최악의 경우의 수가 발생하면 이론상으로는 벨만-포드와의 시간복잡도가 같습니다.
다만, 실제 구현에서는 큐 연산 오버헤드나, 중복노드 삽입 등의 문제로 인해 간혹 SPFA가 더 느려지는 경우도 있습니다.
 
그렇다면 이제 방향을 틀어 벨만-포드 알고리즘이 무엇인지 알아보아야겠죠,,
어떻게 보면 SPFA는 벨만-포드의 변형 알고리즘이기 때문에 순서가 뒤바뀌긴 했지만,,
그래도 어찌저찌 답을 찾아가보는 것이 알고리즘의 몇없는 매력입니다
 
그럼 이제 벨만-포드 알고리즘의 개념과 웜홀 문제의 진짜 답을 알아보겠습니다.
다음 글에서요