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

이 문제는 위상 정렬, 우선순위 큐를 이용해서 풀었다.

 

N개의 문제는 모두 풀어야 하고, 먼저 푸는 것이 좋은 문제는 먼저 풀고, 가능하면 쉬운 문제부터 푸는 3개의 요구사항이 존재하는 문제이다.

 

일단 먼저 푸는 것이 좋은 문제는 먼저 풀어야 하므로 위상 정렬을 사용해야 한다. 여기서 걸리는 것은 가능하면 쉬운 문제부터 푸는 것인데, 이 경우는 우선순위 큐로 작은 숫자부터 뽑아내도록 하여 문제를 쉽게 해결할 수 있었다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

#define MAX 32000

vector<int> edges[MAX + 1];
int N, M;
int incoming[MAX + 1];

void input() {
	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		edges[a].push_back(b);
		incoming[b]++;
	}
}

void solve() {
	priority_queue<int, vector<int>, greater<int>> minPQ;
	
	for (int i = 1; i <= N; i++) {
		if (!incoming[i]) {
			minPQ.push(i);
		}
	}

	while (!minPQ.empty()) {
		int present = minPQ.top();
		minPQ.pop();

		cout << present << " ";

		for (int next : edges[present]) {
			incoming[next]--;

			if (!incoming[next]) {
				minPQ.push(next);
			}
		}
	}
}

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

	input();
	solve();

	return 0;
}