[백준][C++] 1738 골목길 - 벨만포드(bellmanford) 알고리즘

최대한 유리한 경로를 찾는 문제이다. 길을 지날때마다 금품을 잃거나, 금품을 획득하게 된다고 한다. 음의 가중치를 가진 간선이 존재하므로 다익스트라는 불가능이다. 그럼 벨만포드 알고리즘이다.

우리가 아는 알고리즘(다익스트라, 벨만포트, 플로이드 워셜)은 간선을 지날 때마다 비용을 지불한다. 그래서 최소의 비용을 찾는 문제이다. 그런데 1738번은 최대의 금품을 가지는 것을 찾는 문제다. 그래서 벨만포드 알고리즘에 활용하기 위해서 기존의 금품을 획득할 때 +A로 표시하는 것을 반대로 표시한다.(+A -> -A, -A -> +A) 그 것을 통해서 최소의 비용을 찾는 알고리즘인 밸만포드 알고리즘을 사용할 것이다.

최적의 경로가 존재하지 않는 상황은 1->N로 가는 경로를 찾았는데, 그 경로상에서 음수의 싸이클이 있는 경우이다. 민승이는 돈을 계속 주워서 음의 무한대로 발산할 것이다. 하지만 밸만포드알고리즘을 그냥 사용할수는 없다. 왜냐하면 민승이가 못 가는 경로에 음수의 싸이클이 존재하는 경우다. 이 때는 민승이가 가지 못해서 문제없지만, 밸만 포드 알고리즘에서는 음수의 사이클을 찾을 것이다.

민승이가 갈수있는 경로에서 음수의 사이클이 있는 지 확인하기 위해서, 노드 N에서 DFS/BFS를 사용해 갈수있는 노드인지 확인합니다.(visited 배열로 활용)

#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <utility>
#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];
lli dist[MAXN];
int prevRoute[MAXN];
// 1->n까지 가는 경로에 있는지 
bool visited[MAXN] = {false,};
deque<int> st;

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){
        prevRoute[i] = -1;
        dist[i] = INF;
    } 
}

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 bellmanFord(){
    dist[1]=0;
    for(int i=0; i<n-1; ++i){
        for(int j=1; j<=n; ++j){
            int from = j;
            if(dist[from] == INF) continue;
            for(const INFO v : route[j]){
                int next = v.dist;
                int money = v.money;
                if(dist[next] > dist[from] + money){
                    dist[next] = dist[from] + money;
                    prevRoute[next] = from;
                }
            }
        }
    }
    for(int j=1; j<=n; ++j){
        int from = j;
        if(dist[from] == INF) continue;
        for(const INFO v : route[j]){
            int next = v.dist;
            int money = v.money;
            if(visited[next] && (dist[next] > dist[from] + money)){
                return false;
            }
        }
    }
    return true;
}
void getRevConnection(){
    queue<int> q;
    q.push(n);
    visited[n] = true;
    while(!q.empty()){
        int cidx = q.front(); q.pop();
        for(const int& v : RevRoute[cidx]){
            int next = v;
            if(!visited[next]){
                visited[next] = true;
                q.push(next);
            }
        }
    }
}
bool solve(){
    getRevConnection();
    return bellmanFord();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    input();
    bool avail = solve();
    if(avail == false){
        cout << "-1\n";
    }else {
        // cout << -dist[n] <<"\n";
        getHistory(n);
        printHistory();
    }
}