https://www.acmicpc.net/problem/1766
1766번: 문제집
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주
www.acmicpc.net
[필자 사고]
이 문제의 핵심은 위상정렬 알고리즘을 알고 있냐 모르고 있냐 이다.
위상정렬 알고리즘은 쉽게 말해 이 노드와 저 노드가 레벨차이에 따라 정렬해 놓는 알고리즘이다.
또한 이 문제에서 위상정렬에서 사용하는 큐를 보통의 큐가 아닌 우선순위 큐를 사용하여 N이 낮은값부터 출력할 수 있도록 유도했다.
[소스 코드]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> Arr;
vector<int> dist;
int N, M;
void Input() {
cin >> N >> M;
Arr.resize(N + 1);
dist.resize(N + 1, 0);
for (int i = 0; i < M; i++) {
int s, e;
cin >> s >> e;
Arr[s].push_back(e);
dist[e]++;
}
}
void Topological_Sort() {
priority_queue<int, vector<int>,greater<int>> pq;
vector<bool> visited;
visited.resize(N + 1, false);
for (int i = 1; i <= N; i++) {
if (dist[i] == 0) {
pq.push(i);
}
}
while (!pq.empty()) {
int nowIdx = pq.top();
pq.pop();
cout << nowIdx << " ";
for (int nextIdx : Arr[nowIdx]) {
dist[nextIdx]--;
if (dist[nextIdx] == 0) {
pq.push(nextIdx);
}
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Topological_Sort();
}
'백준 > 그래프' 카테고리의 다른 글
백준 14567 c++ "선수과목(Prerequisite)" -[PlusUltraCode] (0) | 2024.02.29 |
---|---|
백준 2623 c++ "음악프로그램" -[PlusUltraCode] (0) | 2024.02.29 |
백준 11562 c++ "백양로 브레이크" -[PlusUltraCode] (0) | 2024.02.29 |
백준 17182 c++ "우주 탐사선" -[PlusUltraCode] (0) | 2024.02.29 |
백준 2610 c++ "회의준비" -[PlusUltraCode] (3) | 2024.02.29 |