[백준 1766] 문제집 (C++)

이 문제는 문제집이 주어질 때, 문제를 푸는 순서를 결정하는 문제이다. 먼저 푸는 게 좋은 문제를 먼저 풀고 가능한 한 쉬운 문제부터 풀어야 한다.

문제들의 관계가 주어지는데, 이는 그래프로 표현이 가능하다.
문제 $U$가 문제 $V$보다 먼저 풀기 좋다면, $U$에서 $V$ 방향으로의 간선을 추가하고 $V$의 진입 차수 deg[v]를 1 증가시켜주면 된다.

그리고, 그래프의 정점들을 문제 조건에 맞춰 출력해야한다. 이는 위상 정렬로 해결이 가능하다. 가능하다면 쉬운 문제부터 풀어야하므로, 풀 수 있는 문제들 중 최소 난이도인 문제를 구해야한다. 이는 우선순위 큐를 이용해서 $O(logN)$으로 구할 수 있다. 만약, 선형자료구조였다면 $O(N^2)$이 걸렸을 것이다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n, m, deg[32001];
vector<int> adj[32001];
priority_queue<int, vector<int>, greater<>> pq;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		deg[v]++;
	}

	for (int i = 1; i <= n; i++) {
		if (!deg[i]) pq.push(i);
	}

	while (!pq.empty()) {
		int cur = pq.top();
		pq.pop();
		cout << cur << " ";
		for (int nxt : adj[cur]) {
			deg[nxt]--;
			if (!deg[nxt]) pq.push(nxt);
		}
	}
}