[백준 1948] 임계경로

위상정렬 + 역추적 문제

 

우선 위상정렬을 통해 각 노드까지 가는데 걸리는 최대시간을 구한다.

이는 위상정렬 돌리면서 dp 배열에 최대값 갱신하면서 돌려주면 된다.

 

그 이후에 해당 노드까지 최대값을 만드는 경로를 찾아야되는데

이걸 종점 노드에서 BFS 돌리면서 역추적을 하면 된다.

이때 queue에 들어가는 노드는 전 dp 값 = 현재 dp값 - 간선 cost 값을 만족하는 노드들이다.

if (dp[next] == total - cost)
{
    ans++;
    // 아직 방문 안했다면
    if (!visited[next])
    {
        visited[next] = 1;
        q.push({next, dp[next]});
    }
}

 

간선을 중복해서 세지 않기 위해 visited를 넣어준다.

 

맨 처음에는 위상정렬 한번으로 끝내려고 했는데 이럴 경우 중복되는 간선을 고려하지 못한다.

그렇다고 지금까지 지나온 간선들을 저장하고 set 같은거로 중복 방지 처리 하는 것은 너무 많은 전처리가 필요하다.

 

마지막에 역추적을 위해 간선 방향이 반대로된 그래프 rgraph 가 필요하다.

따라서 간선 정보 입력받을때 역그래프도 같이 생성해주면 된다.

for (int i = 0; i < M; i++) {
    cin >> start >> end >> cost;
    graph[start].push_back({end, cost});
    // 역추적을 위한 역그래프 저장
    rgraph[end].push_back({start, cost});
    inbound[end]++;
}

 

---

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <tuple>

#define SIZE 10001

using namespace std;

int N, M;
int S, E;
vector<vector<pair<int, int>>> graph(SIZE);
vector<vector<pair<int, int>>> rgraph(SIZE);
int inbound[SIZE];
int dp[SIZE] = { 0, };

void topological()
{
    queue<pair<int, int>> q;
    q.push({S, 0});

    while (!q.empty())
    {
        auto [cur, total] = q.front();
        q.pop();

        int next, cost;
        for (int i = 0; i < graph[cur].size(); i++)
        {
            next = graph[cur][i].first;
            cost = graph[cur][i].second;

            if (total + cost > dp[next])
            {
                dp[next] = total + cost;
            }

            // 더이상 진입차수가 없다면
            inbound[next]--;
            if (inbound[next] == 0)
            {
                q.push({next, dp[next]});
            }
        }
    }
}

void solve()
{
    topological();

    int ans = 0;

    queue<pair<int, int>> q;
    bitset<SIZE> visited;
    q.push({E, dp[E]});
    visited[E] = 1;

    while (!q.empty())
    {
        auto [cur, total] = q.front();
        q.pop();

        int next, cost;
        for (int i = 0; i < rgraph[cur].size(); i++)
        {
            next = rgraph[cur][i].first;
            cost = rgraph[cur][i].second;

            if (dp[next] == total - cost)
            {
                ans++;
                // 아직 방문 안했다면
                if (!visited[next])
                {
                    visited[next] = 1;
                    q.push({next, dp[next]});
                }
            }
        }
    }

    cout << dp[E] << "\n";
    cout << ans;
}

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

    cin >> N;
    cin >> M;

    int start, end, cost;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end >> cost;
        graph[start].push_back({end, cost});
        // 역추적을 위한 역그래프 저장
        rgraph[end].push_back({start, cost});
        inbound[end]++;
    }
    cin >> S >> E;

    solve();

    return 0;
}