BOJ 1948 - 임계경로 링크
(2023.05.01 기준 P5)

문제

무수히 많은 사람들이 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색할 때, 도착 도시에 마지막에 도착하는 시간과 1분도 쉬지 않고 움직이는 사람들이 지나는 도로의 수 출력

알고리즘

모든 도로가 일방통행이며 싸이클이 없는 그래프의 거리는 위상 정렬로 구하면 된다.

풀이

일단 마지막에 도착하는 시간은 위상 정렬로 쉽게 구할 수 있다. 이걸 모르겠다면, BOJ 1005 - ACM Craft 풀이나 BOJ 1516 - 게임 개발 풀이를 보고 오자.

문제는 1분도 쉬지 않고 움직이는 사람들이 지나는 도로의 수다. 일단, 이 말의 뜻을 먼저 알아야 한다.
이런 그래프가 있다. 1번에서 4번으로의 모든 경로를 탐색한다고 했을 때, 1->3->4 경로는 4, 1->2->4 경로는 2가 걸린다. 그러면 1->2->4 경로는 2라는 시간을 쉴 것이고, 1->3->4 경로로 오는 사람은 1분도 쉬지 않고 움직여야 한다.
1->3->4 경로의 도로의 수는 2이므로 위 그래프의 답은 (마지막에 도착하는 시간 2)와 (1분도 쉬지 않고 움직이는 사람들이 지나는 도로의 수 2)가 될 것이다.

결국, 위상 정렬의 결과를 가지고 역추적을 하여 결과와 동일한 결과를 가질 경우 그 간선은 경로에 포함되는 도로이며, 이 도로를 전부 세는 것이다.

예를 들어 이런 과정을 거친다고 생각하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

int dist[10001];
bool visited[10001];
vector<pii> graph[10001], reverse_graph[10001];


// v에서 u로 들어가는 거리와 u의 최대 거리가 같다면 v -> u로 가는 경로가 임계경로
int dfs(int u){
    visited[u] = true;
    int result = 0;
    for (pii there: reverse_graph[u]){
        int v = there.x, w = there.y;
        if (dist[u] == dist[v] + w){
            result++;
            if (!visited[v]) result += dfs(v);
        }
    }
    return result;
}

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

    int n, m, u, v, w, s, e;
    cin >> n >> m;

    int ind[n]; fill(ind, ind + n, 0);
    for (int i = 0; i < m; i++){
        cin >> u >> v >> w;
        graph[--u].push_back({--v, w});
        reverse_graph[v].push_back({u, w}); // 역추적을 위한 역방향 그래프
        ind[v]++;
    }

    cin >> s >> e;
    s--, e--;

    // 진입차수가 0인 정점은 곧 DAG의 시작
    vector<int> q;
    for (int i = 0; i < n; i++) if (!ind[i]) q.push_back(i);

    fill(dist, dist + n, 0); // 각 정점마다의 최대 거리
    while (!q.empty()){
        u = q.back(), q.pop_back();
        for (pii there: graph[u]){
            v = there.x, w = there.y;
            dist[v] = max(dist[v], dist[u] + w); // 최대 거리는 진입하는 정점들의 거리의 최대값
            if (!--ind[v]) q.push_back(v); // 모든 진입이 끝났다면 이제 진출해야 한다.
        }
    }
    cout << dist[e] << '\n';

    // 역추적
    fill(visited, visited + n, false);
    cout << dfs(e);
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(11111)

# v에서 u로 들어가는 거리와 u의 최대 거리가 같다면 v -> u로 가는 경로가 임계경로
def dfs(u):
    visited[u] = True
    result = 0
    for v, w in reverse_graph[u]:
        if dist[u] == dist[v] + w:
            result += 1
            if not visited[v]:
                result += dfs(v)
    return result

n = int(input()); m = int(input())

graph = [[] for _ in range(n)]
reverse_graph = [[] for _ in range(n)] # 역추적을 위한 역방향 그래프
ind = [0] * n
for _ in range(m):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    graph[u].append((v, w))
    reverse_graph[v].append((u, w))
    ind[v] += 1

s, e = map(int, input().split())
s -= 1; e -= 1

# 진입차수가 0인 정점은 곧 DAG의 시작
queue = []
for i in range(n):
    if not ind[i]:
        queue.append(i)

dist = [0] * n # 각 정점마다의 최대 거리
while queue:
    u = queue.pop()
    for v, w in graph[u]:
        dist[v] = max(dist[v], dist[u] + w) # 최대 거리는 진입하는 정점들의 거리의 최대값
        ind[v] -= 1
        if not ind[v]: # 모든 진입이 끝났다면 이제 진출해야 한다.
            queue.append(v)
print(dist[e])

# 역추적
visited = [False] * n
print(dfs(e))