BOJ 1766: 문제집

#BOJ 1766: 문제집

1766번: 문제집

#풀이

위상정렬을 사용하는데 난이도가 쉬운 문제 먼저 풀면 된다.

 

위상정렬을 할 때 queue에 있는 문제를 하나 씩 꺼내서 하는데

 

꺼내기 전에 정렬을 하여 난이도가 가장 작은 문제부터 꺼내면 된다.

 

나는 queue가 아닌 set을 사용했지만 최소힙을 사용해도 된다.

 

priority_queue(최소힙) 을 사용하여 가장 작은 문제부터 꺼낼 수 있다.

 

주석이 최소힙을 사용한 것이고 

주석이 아닌 부분이 set을 사용한 것이다.

 

#코드

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int n, m;
vector<int> adj[32001];
int indeg[32001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b; 
		adj[a].push_back(b);
		indeg[b]++;
	}
	set<int> arr;
	//priority_queue<int, vector<int>, greater<int>> arr;
	for (int i = 1; i <= n; i++) {
		if (indeg[i] == 0) {
			arr.insert(i);//arr.push(i);
		}
	}
	while (!arr.empty()) {
		int a = *arr.begin(); // int a = arr.front(); arr.pop();
		arr.erase(arr.begin());
		for (auto b : adj[a]) {
			indeg[b]--;
			if (indeg[b] == 0)
				arr.insert(b); // arr.push(b);
		}
		cout << a << ' ';
	}
	cout << '\n';
	return 0;
}