[백준] 1766번: 문제집

문제

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

설명

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다. 

위 문제를 풀기 위한 조건이다. 2번 조건을 통해 위상 정렬을 사용해 볼 수 있음을 알 수 있다. 큐를 통한 위상정렬로 접근하였는데, 3번 조건을 만족하기 위해서는 우선순위 큐로 선언해야 한다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> nodes[32001];
int inDegree[32001];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		nodes[a].push_back(b);
		inDegree[b]++;
	}

	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 1; i <= n; i++) {
		if (!inDegree[i])
			pq.push(i);
	}

	for (int i = 0; i < n; i++) {
		int x = pq.top();
		pq.pop();
		cout << x << " ";

		for (int j = 0; j < nodes[x].size(); j++) {
			int y = nodes[x][j];
			inDegree[y]--;
			if (!inDegree[y])
				pq.push(y);
		}
	}
}