BOJ 1948 - 임계영역(그래프, 위상정렬)

 

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

1948번: 임계경로

- 문제에서 2가지를 요구하는데 하나는 DAG가 주어지고 시작노드부터 끝노드까지 가야하는데 여기서 가장 긴 경로를 찾는 것, 다른 하나는 그 경로에 포함된 엣지의 갯수를 찾는 것이다.

* 위상정렬 구현 방식(bfs로 구현할 때) - dfs나 스택도 가능함
1. 각 노드들의 진입 차수 계산
2. 진입 차수가 0인 노드들을 큐에 삽입
3. 큐에서 노드를 꺼내 연결된 간선을 제거
4. 제거로 인해 진입 차수가 0이 된 노드를 큐에 삽입 5. (3)~(4) 번을 반복하며 큐가 비었으면 종료
만약 우선순위가 정해져있는 노드를 먼저 출력해야된다면 우선순위큐를 쓰면 된다

1.  그래프를 그리고, 각 노드별로 indegree를 센 다음, 0인 노드를 큐에 모두 넣어준 다음, 순회를 하면서 다음 노드까지 가는데 걸리는 시간을 계속 거리배열에 최대값을 업데이트 해주면서 탐색해 나간다. 

DAG에서 가장 긴 경로 길이 탐색 순서(노드index 오름차순으로 탐색했을 시)

2. DAG의 역방향 그래프를 그려서 아까 최대값을 업데이트 해주는 것의 반대로 연결된 노드의 엣지 비용이 거리배열간의 차와 같으면
(d[x] - d[y] == w) 이 경로는 거쳐갔던 곳이므로 카운트를 해주는 방식으로 풀 수 있다.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
#define endl '\n'
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int n, m, s, e;
vector<pii> a[10001], b[10001];         // 정방향, 역방향
int ind[10001], ind2[10001], d[10001];  // indegree, 도착시간d[i]
bool check[10001];

// DAG 가장 긴 경로
// 가장 긴 경로에 포함된 엣지 갯수
int main() {
    FASTIO;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        b[v].push_back({u, w});
        ++ind[v];
        ++ind2[u];
    }
    cin >> s >> e;

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (ind[i] == 0) q.push(i);
    }

    // indegree 0인 노드부터 차례대로 업데이트
    while (!q.empty()) {
        int x = q.front();
        q.pop();

        for (auto& [y, w] : a[x]) {
            d[y] = max(d[y], d[x] + w);
            --ind[y];
            if (ind[y] == 0) q.push(y);
        }
    }
    cout << d[e] << endl;  // 순회 끝나는 시간

    for (int i = 1; i <= n; ++i) {
        if (ind2[i] == 0) q.push(i);
    }

    int cnt = 0;
    check[e] = true;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto& [y, w] : b[x]) {
            if (check[x] && d[x] - d[y] == w) {
                check[y] = true;
                ++cnt;
            }

            --ind2[y];
            if (ind2[y] == 0) q.push(y);
        }
    }

    cout << cnt;
    return 0;
}