[백준 알고리즘] 1766번 문제집 문제풀이 c++

1~n개의 문제 중 앞 번호의 문제를 먼저 푸는게 더 좋다.

m개의 선행되어야할 문제 조건이 주어지는데

이 조건을 만족하면서 앞 번호의 문제를 우선적으로 풀 때 결과를 출력하면 된다.

위상정렬을 priority_queue로 구현하면 된다.

cnt배열에 해당 문제에 선행조건이 몇개있는지 저장한다.

order 벡터에 해당 문제가 선행조건인 문제번호를 저장한다.

priority_queue은 번호가 낮을 수록 우선순위를 갖도록

priority_queue<int, vector<int>, greater<int>>로 선언한다.

cnt배열이 0일때, 즉 선행조건이 없는 경우 q에 push한다.

그 후 q가 비어있지 않을 때까지 q의 top을 pop하면서

해당 문제가 선행조건인 문제의 cnt를 감소시키고

cnt값이 0일때의 문제 번호를 p에 push한다.

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int cnt[32001];
vector<vector<int>> order(32001);

int main(){
	int n, m;

	cin >> n >> m;


	int a,b;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		cnt[b]++;
		order[a].push_back(b);
	}

	priority_queue<int,vector<int>, greater<int>> q;
	for(int i=1; i<=n; i++){
		if(cnt[i] == 0){
			q.push(i);
			cnt[i] = -1;
		}
	}

	while(!q.empty()){
		int x = q.top();
		cout << x << " ";
		q.pop();
		for(int i=0; i<order[x].size(); i++){
			if(--cnt[order[x][i]] == 0){
				q.push(order[x][i]);
				cnt[order[x][i]] = -1;
			}
		}
	}

	return 0;
}