C++ / 백준 / 1766 / 문제집

문제

 

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

1766번: 문제집

문제풀이

 

위상정렬 + 우선순위 큐 문제이다.

먼저 풀어야 되는 문제가 있으면 먼저 풀어야 한다.

현재 풀 수 있는 문제가 여러 개라면 번호가 낮은 문제 먼저 풀어야 한다.

위상정렬에서 queue를 쓰는 대신 priority_queue를 사용하면 문제를 쉽게 해결할 수 있다.

 

코드

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

priority_queue<int, vector<int>, greater<int>>pq;
vector<vector<int>>tree;
vector<int>inDegree;
int N;

void topology_sort() {
	for (int idx = 1; idx <= N; ++idx) {
		int num = pq.top();
		cout << pq.top() << ' ';
		pq.pop();

		for (int idx2 = 0; idx2 < tree[num].size(); ++idx2) {
			int next = tree[num][idx2];
			--inDegree[next];
			if (inDegree[next] == 0) pq.push(next);
		}		
	}
}

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

	int M(0);
	cin >> N >> M;
	tree = vector<vector<int>>(N + 1);
	inDegree = vector<int>(N + 1, 0);
	int node1(0), node2(0);
	for (int idx = 0; idx < M; ++idx) {
		cin >> node1 >> node2;
		tree[node1].push_back(node2);
		++inDegree[node2];
	}
	for (int idx = 1; idx <= N; ++idx) {
		if (inDegree[idx] == 0) pq.push(idx);
	}
	topology_sort();
}