반응형
알고리즘 종류
- 우선순위 큐
- 위상정렬
사고 과정
- 순서가 있는 일을 순서대로 나열하는 문제이므로 위상정렬으로 풀 수 있다.
- 가능하면 쉬운 문제부터 풀어야 하므로 우선순위 큐를 이용해서 작은 번호 문제를 먼저 오게 할 수 있다.
- 문제의 예시로 과정을 설명해 보겠다.
* 3번 보다 1번을 먼저 풀고, 4번 보다 2번을 먼저 풀어야 합니다.
* 초기에 진입차수가 0인 번호들이 들어간 우선순위 큐의 모습니다.
* 가장 앞의 3번을 빼고 3번과 연결된 문제 번호들의 진입차수를 하나씩 제거합니다. 그러면 1번이 진입차수 0이 됩니다. 이는 1번 보다 먼저 풀 문제가 없다는 뜻이므로 우선순위 큐에 넣어서 순서대로 풀기로 합니다.
* 가장 앞의 1번을 빼고 1번과 연결된 문제 번호들의 진입차수를 하나씩 제거합니다. 연결된 번호가 없습니다.
* 가장 앞의 4번을 빼고 4번과 연결된 문제 번호들의 진입차수를 하나씩 제거합니다. 그러면 2번이 진입차수 0이 됩니다.
* 마지막 남은 2번을 꺼내고 종료됩니다.
구현(C++)
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
50
51
52
53
54
55
56
57
58
59
60
|
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;
vector<int> res; // 순서 결과 담는 배열
vector<int> inDegree; // 진입차수 배열
vector<vector<int> > edges; // 먼저 푸는 문제를 담는 배열
void topologySort(){
// 쉬운 문제(작은 번호 문제)부터 풀어야 하므로 가장 작은 번호 문제가 먼저오게 한다.
priority_queue<int> pq;
for(int i=1; i<=n; i++)
if(inDegree[i]==0)
pq.push(-i);
for(int i=1; i<=n; i++){
if(pq.empty()) return;
int seq = -pq.top();
res.push_back(seq);
pq.pop();
for(int j=0; j<edges[seq].size(); j++){
int next_seq = edges[seq][j];
// 진입 차수가 0이 되면, 즉 먼저 풀어야 할 문제를 다 풀면 우선순위 큐에 넣어준다.
// 우선순위 큐에 들어가면, 가장 작은 문제 번호 부터 풀게 된다.
if(--inDegree[next_seq] == 0)
pq.push(-next_seq);
}
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
edges.resize(n+1);
inDegree.resize(n+1);
int a, b;
for(int i=0; i<m; i++){
cin >> a >> b;
edges[a].push_back(b);
inDegree[b]++;
}
topologySort();
for(int i=0; i<n; i++) cout << res[i] << " ";
}
|
cs |
시행착오
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
[백준][C++] 2250 트리의 높이와 너비 (0) | 2021.03.31 |
---|---|
[백준][C++] 17244 아맞다우산 (0) | 2021.03.31 |
[백준][C++] 1715 카드 정렬하기 (0) | 2021.03.29 |
[백준][C++] 1400 화물차 (0) | 2021.03.27 |
[백준][C++] 14950 정복자 (0) | 2021.03.27 |