백준 1766 c++ "문제집" -[PlusUltraCode]

https://www.acmicpc.net/problem/1766

1766번: 문제집

[필자 사고]

이 문제의 핵심은 위상정렬 알고리즘을 알고 있냐 모르고 있냐 이다.

 

위상정렬 알고리즘은 쉽게 말해 이 노드와 저 노드가 레벨차이에 따라 정렬해 놓는 알고리즘이다.

 

또한 이 문제에서 위상정렬에서 사용하는 큐를 보통의 큐가 아닌 우선순위 큐를 사용하여 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();
	
}