[백준/C++] 1738번: 골목길(G2)

 

문제

https://www.acmicpc.net/problem/1738

1738번: 골목길

 

 

사용한 알고리즘

2022.02.14 - [PS/Algorithm] - [알고리즘 개념정리] 10. 최단경로 알고리즘

-> 벨만-포드

 

 

풀이 

음의 간선이 있으니 벨만포드 알고리즘을 사용하여 풀어보자.
이 문제에서는 금품의 양이 최대가 되는 경로를 구하는 중이므로 
입력할 때 간선의 부호를 반대로 넣은 후, 음의 사이클 여부를 판단해주면 된다.

다만, 사이클이 있다고 해서 무조건 -1을 출력하는 것은 아니다. 이것때문에 맞왜틀하다가 결국 구글링으로 알아냈다.ㅜ
최적경로에 사이클이 포함되어야 -1을 출력한다.
음의 사이클이 있더라도 도착지점까지 가는 경로에 포함되지 않는다면 영향을 미치지 않는다.

사이클에서 도착지점까지 가는 경로가 있는지 판단하기 위해 vector<int>rev를 사용했다.
a에서 b로 가는 간선을 입력받을 때, rev[b].push_back(a)를 해준다.
그 후, n번 노드 부터 출발하여 경로를 거스르며 들리는 노드마다 visit체크를 해준다.

벨만포드 함수에서 마지막 iteration에 갱신되는 노드가 visited라면 -1을 출력한다.

 

 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
const int MAX_V=101;
int n,m,a,b,c,cycle=0;
vector<pair<int,int>> adj[MAX_V];
vector<int> rev[MAX_V];
int dist[MAX_V],pre[MAX_V],vis[MAX_V];

void bellman_ford(int st){
    fill(dist, dist+MAX_V, INT_MAX);
    fill(pre, pre+MAX_V, 0);
    dist[st]=0;
    for(int iter=1; iter<=n; iter++){
        //모든 간선 확인작업을 n번 반복
        for(int cur=1; cur<=n; cur++){
            if(dist[cur]==INT_MAX) continue; //아직 이어지지 않은 정점은 패스
            for(auto &u:adj[cur]){
                int next=u.first, cost=u.second;
                if(dist[next]>dist[cur]+cost){
                    dist[next]=dist[cur]+cost;
                    pre[next]=cur; //경로저장
                    if(iter==n && vis[next]) cycle=1; //사이클이 있고 n번 노드까지 가는 길이 있으면 -1출력
                }
            }
        }
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        adj[a].push_back({b, -c});
        rev[b].push_back(a); //경로를 거꾸로 저장
    }

    //n에서 부터 출발해서 경로를 거스르며 vis체크 -> i번 노드에서 n번노드까지 갈 수 있다면 vis[i]=1
    queue<int> q;
    q.push(n);
    vis[n]=1;
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        for(int i=0; i<rev[cur].size(); i++){
            int next=rev[cur][i];
            if(!vis[next]){
                vis[next]=1;
                q.push(next);
            }
        }
    } 

    bellman_ford(1);

    if(cycle){
        cout<<-1;
    }
    else{
        vector<int> ans;
        int idx = n;
        while (idx >= 1) {
            ans.push_back(idx);
            idx = pre[idx];
        }
        reverse(ans.begin(), ans.end());
        for (auto &k:ans) cout << k << " ";
    }
    return 0;
}