해당 포스팅은 나동빈님의 25. 위상 정렬(Topology Sort) 포스팅을 참고하여 쓰여졌습니다.

[개념]

위상 정렬이란 '반드시 지켜야 하는 순서'에 따라 정렬하는 방식을 말한다. 예를 들어 저녁 식사를 위한 요리 재료를 사는 과정을 그래프로 표현해보자.

마트에 가지 않으면 물건을 고를 수도, 직원에게 카드를 건넬 수도 없다. 또한 물건을 고르지 않으면 물건을 구매할 수 없고 마찬가지로 돈을 내지 않으면 물건을 골랐더라도 구매할 수 없다. 이렇게 반드시 지켜야 하는 순서가 있을 때 어떤 순서로 일을 처리해야 하는지 알려주는 것이 위상 정렬이다.

같은 특징을 가진 아래의 그래프를 보자.

최종 7번 노드에 방문하기 위해서 어떤 순서로 노드들을 거쳐야 하는지 위상정렬로 표현할 수 있다. 이때 주의해야 할 것은 그래프가 '방향이 있는 비순환 그래프'여야 한다는 것이다.

위상정렬은 다음의 과정을 반복한다. 필자는 큐를 이용하여 위상정렬을 구현하였다.

• 진입 간선 수가 0인 노드를 선택하고 큐에 삽입한다.
• 큐에서 노드를 꺼내고 해당 노드에 연결된 간선을 모두 제거한다.

· 과정

위 예시 그래프에 이 과정을 적용하면 처음 진입 간선이 존재하지 않는 노드는 1 뿐이므로 1을 큐에 넣는다. 이후 큐에서 노드를 꺼내고 해당 노드에 연결된 간선 즉, 1에 연결된 2와 5로 진입하는 간선을 제거한다.

2와 5는 1로부터의 진입 간선을 제외하곤 다른 진입 간선이 존재하지 않으므로 진입 간선 수가 0이 되었다. 따라서 2와 5를 큐에 삽입한다. 이후 2가 큐에서 빠져나오고, 간선을 제거하면 3이 큐에 삽입된다.

이후 특이 경우가 나오는데, 5를 큐에서 빼낸 뒤 5에 연결된 모든 간선을 제거하여도 진입 간선 수가 0이 된 새로운 노드가 나타나지 않는다. 5가 가리키던 노드 6은 노드 4에서부터 진입하는 또다른 간선이 존재하기 때문이다. 따라서 큐에 삽입하기 위한 조건을 만족하지 못했으므로 생략하고 다시 큐에서 노드 4를 꺼낸다.

4를 꺼내고 모든 간선을 제거한 후 비로소 6의 진입 간선 수가 0이 되었다. 이후 차례대로 6, 7을 방문하면 목표였던 7번 노드에 도달하기 위한 순서 1 2 5 3 4 6 7이 완성된다.

이를 소스 코드로 표현하면 다음과 같다.

[소스코드]

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

int n, k;

std::queue<int> q;

std::vector<int> adjacency[1001];	// 특정 노드가 가리키는 노드들의 집합 변수
int inDegree[1001] = { 0, };		// 각 노드의 진입 간선 수를 저장한 변수

std::vector<int> sortedNodes;		// 위상 정렬로 결정된 방문 순서를 저장한 변수

void topology_sort() {
	for (int count = 1; count <= n; count++) {
		if (inDegree[count] == 0) {
			q.push(count);
			sortedNodes.push_back(count);
		}
	}

	for (int count = 1; count <= n; count++) {
		if (q.empty()) {
			std::cout << "Cyclic graph\n";
		}

		int curNode = q.front();
		q.pop();

		for (auto adj : adjacency[curNode]) {
			if ((--inDegree[adj]) == 0) {
				q.push(adj);
				sortedNodes.push_back(adj);
			}
		}
	}
}

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

	std::cin >> n >> k;

	int firstNode, secondNode;
	for (int count = 0; count < k; count++) {
		std::cin >> firstNode >> secondNode;
		adjacency[firstNode].push_back(secondNode);
		inDegree[secondNode]++;
	}

	topology_sort();

	for (auto nodes : sortedNodes) {
		std::cout << nodes << " ";
	}
	std::cout << "\n";
}