문제 이해
- N: 문제의 개수 (1 ~ 32,000, 10^4)
- M: 정보의 개수 (1 ~ 100,000, 10^5)
- 문제는 난이도 순서로 출제
- N개의 문제는 모두 풀어야 한다
- 먼저 풀으면 좋은 문제는 먼저 풀어야 한다
- 가능하면 쉬운 문제부터 풀어야 한다
문제 풀이
먼저 풀면 좋은 문제가 주어진다는 것은
특정 순서가 주어진 그래프의 전체 순서를 결정한다는 것과 같다.
즉, 위상 정렬을 사용해주면 쉽게 풀 수 있다.
다만, 이 문제에서 주의할 점은
'가능하면 쉬운 문제부터 풀어야 한다'는 점이다.
보통의 위상 정렬은 여러 개의 경우의 수가 가능하지만
위의 문구로 인해 이 문제는 한 가지 경우의 수만 나올 것이다.
가능하면 쉬운 문제를 풀기 위해
각 정점으로 들어가는 간선의 개수를 체크할 때 1개의 정점만 큐에 넣고,
큐에서 하나를 빼고난 뒤에 각 정점을 매번 체크해주어 1개씩 큐에 넣어주어야 한다.
큐에 넣어준 정점의 경우 다시 큐에 넣지 않기 위해 매우 큰 값으로 초기화해준다.
전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> v[32005];
int inDegree[32005];
queue<int> q;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
v[a].push_back(b);
inDegree[b]++;
}
for(int i = 1; i <= n; i++){
if(inDegree[i] == 0){
inDegree[i] = 100005;
q.push(i);
break;
}
}
while(!q.empty()){
int now = q.front();
q.pop();
cout<<now<<" ";
int size = v[now].size();
for(int i = 0; i < size; i++){
int next = v[now][i];
inDegree[next]--;
}
for(int i = 1; i <= n; i++){
if(inDegree[i] == 0){
inDegree[i] = 100005;
q.push(i);
break;
}
}
}
return 0;
}
'알고리즘 별 문제 정리 > 위상정렬' 카테고리의 다른 글
[C++] 백준 2056: 작업 (0) | 2024.08.25 |
---|---|
[C++] 백준 2623: 음악프로그램 (0) | 2024.08.25 |
[C++] 백준 2252: 줄 세우기 (0) | 2024.08.24 |
[C++] 백준 1516: 게임 개발 (0) | 2024.08.02 |
[C++] 백준 1005: ACM Craft (0) | 2024.07.18 |