[백준] 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);
		}
	}
}