백준 1766번: 문제집

[문제 링크]

1766번: 문제집

---

어떤 문제를 풀기 위해서 먼저 풀어야 하는 문제가 있다고 한다. 이때 어떤 문제는 먼저 풀어야 하는 문제에 의존적이라고 할 수 있다.

이 문제처럼 정점끼리 서로 의존성이 존재하는 경우 위상정렬을 통해 올바른 순서를 찾을 수 있다.

 

이전까지는 DFS를 수행한 결과를 역순으로 출력하여 위상정렬을 수행하는 방법만 알고 있었는데,

이 문제를 통해 들어오는 간선의 개수(in degree)를 이용하여 위상정렬을 수행하는 방법을 새롭게 알게 되었다.

 

ps// 아래 블로그를 참고하여 풀었는데, 위상정렬에 대한 설명이 잘 되어있는 것 같다.

jason9319.tistory.com/93

Topological Sort(위상 정렬)

---

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

vector<int> adj[32001];
int indegree[32001];

vector<int> topologicalSort(int N) {
	priority_queue<int> pq;
	for (int i = 1; i <= N; i++)
		if (indegree[i] == 0)
			pq.push(-i);
	
	vector<int> order;
	while (!pq.empty()) {
		int here = -pq.top();
		pq.pop();

		order.push_back(here);
		
		for (auto x : adj[here]) {
			indegree[x]--;
			if (indegree[x] == 0)
				pq.push(-x);
		}
	}
	return order;
}

int main(void) {
	int N, M;
	cin >> N >> M;

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

	vector<int> result = topologicalSort(N);

	for (auto x : result)
		cout << x << ' ';

	return 0;
}