[Baekjoon] 1766번: 문제집

🥅 문제

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

 

🔍 설계

먼저 푸는 것이 좋은 문제를 먼저 푼다는 것에서 두 문제 간의 순서가 정해져 있고, 위상 정렬임을 쉽게 파악할 수 있었다.

 

추가로 우선순위가 같은 경우, 쉬운 문제를 먼저 풀기 때문에 진입 차수가 0이 되었을 때, 바로 출력하지 말고, greater 우선순위 큐를 이용하여 진입 차수가 0인 문제 번호를 담아 빼낼 때마다 출력하도록 한다.

 

👊 풀이

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

int n, m, a, b;
priority_queue<int, vector<int>, greater<int>> pq;
vector<int> degree(100001);
vector<vector<int>> adj_list(100001);

void topology_sort() {
	for (int i = 1; i <= n; i++) {
		if (degree[i] == 0) {
			pq.push(i);
		}
	}

	while (!pq.empty()) {
		int cur = pq.top();
		pq.pop();
		cout << cur << " ";

		int size = adj_list[cur].size();
		for (int i = 0; i < size; i++) {
			int next = adj_list[cur][i];
			degree[next] -= 1;
			if (degree[next] == 0) {
				pq.push(next);
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		degree[b] += 1;
		adj_list[a].push_back(b);
	}

	topology_sort();
	
	return 0;
}