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

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

https://www.acmicpc.net/problem/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 #include #include #include using namespace std; typedef pair pii; #define endl '

' #define FASTIO cin.tie(nullptr)->sync_with_stdio(false) int n, m, s, e; vector 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 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; }

from http://ellerymoon.tistory.com/59 by ccl(A) rewrite - 2021-08-20 21:26:25