[백준] 1766 문제집 c++

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

1766번: 문제집

 

풀이과정

이 문제는 조건 3개를 잘 기억해야 한다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

문제를 읽어보면 1번 문제가 쉬운 문제이고 N번 문제가 가장 어려운 문제라고 하였으니  
우선순위 큐를 떠올려 봐야한다. 원래 우선순위 큐는 내림차순이므로, 오름차순으로 구현을 했다.

 

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

int N, M, A, B;
int indegree[32001];

priority_queue <int, vector <int>, greater <int>> pq; // 오름차순
vector <int> v[32001];

void topologySort() {
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			pq.push(i);
		}
	}
	while (!pq.empty()) {
		int now = pq.top();
		pq.pop();

		cout << now << " ";

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			indegree[next]--;

			if (indegree[next] == 0) {
				pq.push(next);
			}
		}
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> A >> B;
		v[A].push_back(B);
		indegree[B]++;
	}
	topologySort();
}