[백준 문제풀이] 백준 c++ 1766 문제집

 

위상정렬과 우선순위 큐를 활용하여 풀 수 있는 문제

 

1. 선수 문제를 풀어야 한다는 조건

2. 최대한 낮은 번호의 문제를 먼저 풀어야 한다는 조건

 

이 두개를 지키기 위해서는 우선순위 큐가 꼭 필요하다.

 

-> 종속되는 문제들을 제외한 독립적인 문제를 우선순위 큐에 넣어주고, 내부에서 종속성을 해제하고 다음 값을 우선순위 큐에 다시 넣어준다.

 

무한 반복이 그래프가 아니기 때문에 독립적인 문제가 하나는 존재하므로, 그것들을 오름차순으로 우선순위 큐에 넣어준다. 

 

그와 관계된 종속 문제를, 해제할 때마다 우선순위 큐에 넣어주므로 조건 2도 만족할 수 있다.

 

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

std::vector<std::vector<int>> info;
std::priority_queue<int, std::vector<int>, std::greater<int>> q;
int check[100001] = {};

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, m;
	std::cin >> n >> m;

	info.assign(n+1, std::vector<int>(0));

	int a, b;
	for (int i = 0; i < m; i++) {
		std::cin >> a >> b;

		info[a].push_back(b);
		check[b]++;
	}

	for (int i{ 1 }; i <= n; i++) {
		if (!check[i]) q.push(i);
	}

	while (!q.empty()) {
		int k = q.top();
		q.pop();

		std::cout << k << " ";

		for (int i{ 0 }; i < info[k].size(); i++) {
			int t = info[k][i];
			check[t]--;

			if (!check[t]) q.push(t);
		}
	}

	std::cout << "\n";
}