백준 14567 선수과목 (Prerequisite) | C++
이번 포스팅은 백준 14567번 선수과목 (Prerequisite)입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
14567번: 선수과목 (Prerequisite)
3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.
www.acmicpc.net
기본 알고리즘
위상 정렬 (Topological Sort)
풀이
위상 정렬하면서 출력 배열(과목 번호가 인덱스)에 수강 학기 수를 저장한다.
1학기 부터 시작하므로 result 배열을 1로 초기화 한다.
q 1 4 6
result[i] 1 1 1
cur = 1
q 1 4 6 2 3
result[i] 1 1 1
next = 2
result[2] < result[1]+1 이므로 result[2] = 2
q 1 4 6 2 3
result[i] 1 1 1 2
next = 3
result[3] < result[1]+1 이므로 result[3] = 2
q 1 4 6 2 3
result[i] 1 1 1 2 2
cur = 4
q 1 4 6 2 3 5
result[i] 1 1 1 2 2
next = 5
result[5] < result[4]+1 이므로 result[5] = 2
q 1 4 6 2 3 5
result[i] 1 1 1 2 2 2
cur = 6
q 1 4 6 2 3 5
result[i] 1 1 1 2 2 2
cur = 2
q 1 4 6 2 3 5
result[i] 1 1 1 2 2 2
next = 5
result[5] < result[2]+1 이므로 result[5] = 3
q 1 4 6 2 3 5
result[i] 1 1 1 2 2 3
cur = 3
q 1 4 6 2 3 5
result[i] 1 1 1 2 2 3
cur = 5
q 1 4 6 2 3 5
result[i] 1 1 1 2 2 3
전체 코드
|
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
49
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 1001;
vector<int> adj[MAX];
int inDeg[MAX];
queue<int> q;
int result[MAX];
int main() {
int N, M;
cin >> N >> M;
int a, b;
for (int i = 0; i < M; i++) {
cin >> a >> b;
adj[a].push_back(b);
inDeg[b]++;
}
for (int i = 1; i <= N; i++) {
if (inDeg[i] == 0) {
q.push(i);
}
result[i] = 1; //1학기부터 시작(초기화)
}
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < adj[cur].size(); i++) {
int next = adj[cur][i];
inDeg[next]--;
if (inDeg[next] == 0) {
q.push(next);
result[next] = max(result[next], result[cur] + 1); //★
}
}
}
for (int i = 1; i <=N; i++) {
cout << result[i] << " ";
}
return 0;
}
|
cs |
