[알고리즘] 위상정렬

위상 정렬은 선행되어야 하는 조건들이 주어지고 그 수들의 순서를 구해야 할 때 사용할 수 있다.

 

위상 정렬을 활용하기 위해서는 진입 차수와 인접한 노드를 알아야 한다. 진입 차수란 해당 노드가 실행되기 위해서 선행되어야 하는 노드의 개수를 뜻한다.

 

진입차수가 주어지면 진입 차수가 0 인 노드들부터 큐에 넣는다. 그다음 큐에서 원소 하나씩 확인하게 되는데 큐에서 pop 된 순서가 최종 순서가 되며 pop 이 되었다면 인접한 노드들의 진입 차수를 1 감소시킨다. 이때 인접한 노드의 진입 차수가 0이 되었다면 큐에 추가하여 자신의 순서가 확정되길 기다린다.

 

아래의 코드는 백준 2252번 줄세우기의 코드이다

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

using namespace std;

int n,m, inDegree[32001] = { 0 };
vector<int> a[32001];

void topologySort() {
	int result[100001];
	queue<int> q;

	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) 
			q.push(i);
	}
	for (int i = 1; i <= n; i++) {
		if (q.empty()) {
			cout << "ERROR";
			return;
		}
		int x = q.front();
		q.pop();
		result[i] = x;
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (--inDegree[y] == 0)
				q.push(y);
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << result[i] << ' ';
	}
}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		a[t1].push_back(t2);
		inDegree[t2]++;
	}
	topologySort();
	return 0;
}