[백준][C++] 1738 골목길 - SPFA (Shortest Path Faster Algorithm) 알고리즘

벨만포드 알고리즘은 모든 노드에 대해서 업데이트를 하는 것에 반해, SPFA는 업데이트된 노드와 그 노드에 연결된 간선만 확인하고 업데이트하는 것이다.

O(VE)로 벨만 포드 알고리즘과 동일하지만, 특정 경우에 O(V+E)에 빠르게 연산가능하다는 점이다.

밸만포드 알고리즘과 동일하게 visited 변수를 활용해 1->n 루트에서 음수의 사이클이 있는지 확인한다.

큐와 큐에 있는지 확인하는 배열(inQ)를 활용해 업데이트한 노드를 큐에 넣을 수 있도록하고, cycle[MAXN] 변수를 두어 노드를 n번이상 방문하면 벨만포드에서 n번째 순회를 했을 때랑 동일하게 음수의 사이클이 있다고 판단한다. 

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#define MAXN 100+1
typedef long long int lli;
using namespace std;
const lli INF = (lli)1e15; 
typedef struct INFO{
    int dist,money;
}INFO;
int n,m;
vector<INFO> route[MAXN];
vector<int> revRoute[MAXN];
int prevRoute[MAXN];
bool visited[MAXN] = {false,};
lli dist[MAXN];
deque<int> st;

queue<int> q;
int cycle[MAXN];
bool inQ[MAXN];

void input(){
    int u,v,w;
    cin >> n >> m;
    for(int i=0; i<m; ++i){
        cin >> u >> v >> w;
        route[u].push_back({v,-w});
        revRoute[v].push_back(u);
    }
    for(int i=1; i<=n; ++i) {
        dist[i] = INF;
        prevRoute[i] = i;
    }
    memset(cycle,0,sizeof(cycle));
    memset(inQ,false,sizeof(inQ));
}


void getHistory(int vertex){
    int node = vertex;
    while(true){
        st.push_front(node);
        if(node == 1) break;
        node = prevRoute[node];
    }
}
void printHistory(){
    for(const int& v : st){
        cout << v << " ";
    } cout << "\n";
}
bool spfa(){
    dist[1] =0;
    q.push(1); inQ[1] = true;
    cycle[1]++;
    while(!q.empty()){
        int here = q.front(); q.pop();
        inQ[here] = false;
        if(cycle[here] >n || dist[here] == INF) continue;
        for(const INFO& tmp : route[here]){
            int next = tmp.dist;
            int cost = tmp.money;
            // cout << "next : " << next << " " << (dist[next] > dist[here] + cost) << "\n";
            if(dist[next] > dist[here] + cost){
                dist[next] = dist[here] + cost;
                prevRoute[next] = here;
                if(inQ[next] == false){
                    q.push(next); inQ[next] = true;
                    cycle[next]++;
                    if(visited[next] && cycle[next] >=n ){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

void getRevConnection(){
    queue<int> q;
    q.push(n);
    visited[n]= true;
    while(!q.empty()){
        int here = q.front(); q.pop();
        for(const int& v : revRoute[here]){
            int next = v;
            if(visited[next] == false){
                visited[next] = true;
                q.push(next);
            }
        }
    }
}
void solve(){
    getRevConnection(); // 이부분이 핵심
    bool result = spfa();
    if(result == false){
        cout << "-1\n";
    }else {
        // cout << -dist[n] << "\n";
        getHistory(n);
        printHistory();
    }
    
}
bool BFS(){
    queue<int> qSearch;
    bool visited[n+1];
    memset(visited,false,sizeof(visited));
    qSearch.push(1);
    visited[1] = true;
    while(!qSearch.empty()){
        int here = qSearch.front(); qSearch.pop();
        for(const INFO& v: route[here]){
            // cout << "v.dist : " << v.dist << "\n";
            if(visited[v.dist]) continue;
            if(v.dist == n) return true;
            else {
                visited[v.dist] = true;
                qSearch.push(v.dist);
            }
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    input();
    bool canReach = BFS();
    if(canReach == true) solve();
    else cout << "-1\n";
}