반응형
https://www.acmicpc.net/problem/14567
14567번: 선수과목 (Prerequisite)
3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/72
[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)
1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방
rudalsd.tistory.com
1. 선수 과목과 후수 과목으로 이어지는 단방향 그래프를 만들어줍니다.
2. 1과 동시에 선수과목이 몇 개 필요한지 cnt[ i ]++를 통해 저장해 주고, cnt[ i ]가 0이면 queue에 넣어줍니다.
3. queue를 돌면서 cnt[ i ]가 0이면 계속 queue에 넣어주면서 선수과목이 몇 개 필요한지 ans에 저장합니다.
4. 1부터 N까지 ans[ i ]를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include<iostream> #include<vector> #include<queue> using namespace std; int N, M; int cnt[1001]; int ans[1001]; vector<int> list[1001]; int main() { scanf("%d %d", &N, &M); queue<int> q; for (int i = 0; i < M; i++) { int A, B; scanf("%d %d", &A, &B); list[A].push_back(B); cnt[B]++; } for (int i = 1; i <= N; i++) { if (cnt[i] == 0) { q.push(i); ans[i] = 1; } } while (!q.empty()) { const int cur = q.front(); q.pop(); for (auto& next : list[cur]) { cnt[next]--; if (cnt[next] == 0) { q.push(next); ans[next] += ans[cur] + 1; } } } for (int i = 1; i <= N; i++) { printf("%d ", ans[i]); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 15422번 - Bumped! (C++) (0) | 2023.03.24 |
|---|---|
| [ 백준 ] 21940번 - 가운데에서 만나기 (C++) (0) | 2023.03.23 |
| [ 백준 ] 4963번 - 섬의 개 (C++) (0) | 2023.03.21 |
| [ 백준 ] 10723번 - 판게아 1 (C++) (0) | 2023.03.20 |
| [ 백준 ] 7044번 - Bad Cowtractors (C++) (0) | 2023.03.19 |