[백준]1766 - 문제집

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

1766번: 문제집

처음에 단순히 위상 정렬만 사용하면 되는데 왜 골드 2나 레이팅 돼 있는 건가 생각해서 조금 당황했지만,

가능하면 쉬운 문제부터 풀어야 한다.

이 문장 하나 때문인 것 같다.

 

위상 정렬의 결과로 순서를 매길 수 없는 문제들이라면, 우선순위 큐를 이용해서 무조건 작은 문제들이 먼저 풀리게끔 만들어 주면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m;
int inp[32001];
int main() {

	cin >> n >> m;
	vector<vector<int>> v(n + 1);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		inp[b]++;
		v[a].push_back(b);
	}
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 1; i <= n; i++) {
		if (inp[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int a = q.top();
		q.pop();
		cout << a << ' ';

		for (int i = 0; i < v[a].size(); i++) {
			if (--inp[v[a][i]] == 0) {
				q.push(v[a][i]);
			}
		}
	}
}