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

1766번: 문제집 (acmicpc.net)

1766번: 문제집

우선순위 큐를 이용하면 쉽게 풀 수 있는 문제이다. 오름차순으로 정렬하는 우선 순위 큐를 정의한다음 해당 번호의 문제가 풀리기 위해 풀어야할 문제 개수를 저장하는 depth 배열을 통해 queue에 이 번호를 집어 넣을지 결정하면 된다. 즉, 앞서 풀어야할 문제 수가 0개인 문제를 queue에 넣어주면 된다.이후 queue의 top을 꺼내오면 된다.

 

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

using namespace std; 

int N,M;
int depth[32001];
vector<int> v[32001];
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	cin>>N>>M;
	int f, s;
	for(int i = 0; i<M; i++)
	{
		cin>>f>>s;
		v[f].push_back(s);
		depth[s]++;
	}
	for(int i = 1; i<=N; i++)
	{
		if(!depth[i])
			pq.push(i);
	}
	while(!pq.empty())
	{
		int tmp = pq.top();
		pq.pop();
		cout<<tmp<<" ";
		for(int i =0; i<v[tmp].size(); i++)
		{
			if(!--depth[v[tmp][i]])
				pq.push(v[tmp][i]);
		}
	}
	return 0;
}