[C/C++] 백준 1766번 - 문제집

✏️ 문제 링크

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

1766번: 문제집

 

✏️ 문제 설명

✏️ 문제 풀이

기본적인 위상 정렬 문제이고 문제에서 주어진 "가능하면 쉬운 문제부터 풀어야 한다"의 조건을 주의해야 합니다.

문제의 숫자가 높아질수록 난이도가 올라가므로 우선순위 큐를 오름차순으로 정렬해서 큐를 돌려주면 됩니다.

 

✏️ 문제 코드

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


vector<vector<int>>mlist;
vector<int>indegree;
priority_queue<int, vector<int>, greater<int>>q;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	mlist.resize(N + 1);
	indegree.resize(N + 1);


	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		mlist[start].push_back(end);
		indegree[end]++;
	}
	
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0)
			q.push(i);
	}

	vector<int>ans;
	while (!q.empty()) {
		int node = q.top();
		ans.push_back(node);
		q.pop();
		for (int next : mlist[node]) {
			indegree[next]--;
			if (indegree[next] == 0)
				q.push(next);
		}
	}
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";
}