[백준] 1738번 - 골목길

 

문제

1738번 골목길: https://www.acmicpc.net/problem/1738

오랫만에 고통 좀 받은 문제, 얼른 풀고 SCC공부하려 했는데 시간 다 뺏김 ㅜㅜ

 

양 또는 음의 가중치를 가지는 그래프에서 사이클을 판별하고 경로 추적을 하는 문제 (그래프, 벨만-포드)

벨만 포드는 몰라서, SPFA로 품

 

 

 

풀이

1. 역방향 그래프를 생성해서 BFS를 돌려 해당 정점에서 N정점에 도달 가능한지 여부를 판단

만약 해당 정점이 N정점에 도달하지 않는 정점이라면 1에서 N정점간의 비용을 구할 때 고려하지 않아도 된다. (사이클이 존재하지만 정답을 출력하는 경우!)

2. SPFA 돌리기, SPFA 경로추적은 몰라서 그냥 다익스트라처럼 비슷하게 추적함

if(check[nxt.n] == 0) continue; 와 같이 1번의 경우 고려X

3. 스택으로 간선 출력

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <string>
using namespace std;
int N, M;
int check[101];
int visitedCnt[101];
int visited[101];
struct Node {
    int n, cost;
};
vector<Node> graph[101];
vector<Node> rev[101];
int answer[101];
vector<int> path[101];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int fg = 0;
    cin >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == b) fg = 1;
        graph[a].push_back({ b, -c });
        rev[b].push_back({ a, -c });
    }

    for (int i = 1; i <= N; ++i) answer[i] = 1987654321;
   
    // 역방향으로 각 노드가 도착점에 도달 가능한지 검사
    queue<int> q;
    q.push(N);
    check[N] = 1;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < rev[now].size(); ++i)
        {
            Node nxt = rev[now][i];
            if (check[nxt.n]) continue;
            check[nxt.n] = 1;
            q.push(nxt.n);
        }
    }
    if (check[1] == 0) {
        //시작점이 도착점에 도달 불가한 경우
        cout << -1;
        return 0;
    }

    // SPFA
    q.push(1);
    answer[1] = 0;
    visited[1] = 1;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        visitedCnt[now]++;
        visited[now] = 0;
        if (visitedCnt[now] >= N) {
            cout << -1;
            return 0;
        }
        for (int i = 0; i < graph[now].size(); ++i)
        {
            Node nxt = graph[now][i];
            int nxtCost = answer[now] + nxt.cost;
            if (check[nxt.n] == 0) continue;
            if (nxtCost > answer[nxt.n]) continue;
            else if (nxtCost == answer[nxt.n]) {
                path[nxt.n].push_back(now);
            }
            else {
                path[nxt.n].clear();
                path[nxt.n].push_back(now);
                answer[nxt.n] = nxtCost;
                if (visited[nxt.n] == 0)
                {
                    visited[nxt.n] = 1;
                    q.push(nxt.n);
                }
            }
        }
    }
    
    stack<int> ans;
    for (int i = N; i != 1; i = path[i][0]) {        
        ans.push(i);
    }
    cout << "1 ";

    while (!ans.empty()) {
        cout << ans.top() << " ";
        ans.pop();
    }
    return 0;
}