[알고리즘] 위상정렬(Topology Sort) c++

위상정렬(Topology Sort)이란?

위상정렬은 사이클이 없는 방향 그래프(DAG)에서 작업의 순서(조건)가 정해져 있는 경우 전체 작업들의 순서를 정렬하는 알고리즘이다.
 
방탈출 게임을 예시로 설명하겠다.

방탈출 게임

위 그래프를 보면
 1번문 열쇠3을 얻기 위해서는 1번문 열쇠1, 열쇠2가 필요하다.
 1번문을 열기 위해서는 1번문 열쇠1, 열쇠2, 열쇠3이 모두 필요하다.
 탈출을 하기 위해서는 1번 문을 통과해야 하고, 탈출 열쇠를 얻어야 한다.
 
탈출 시나리오는 다음과 같다.
 1.   시작
 2.   열쇠1 또는 열쇠2를 얻는다.
 3.   남은 열쇠1 또는 열쇠2를 얻는다.
 4.   열쇠1과 열쇠2를 통해 열쇠3을 얻는다.
 5.   열쇠1, 열쇠2, 열쇠3을 이용해 1번 문을 통과한다.
 6.   탈출 열쇠를 얻는다.
 7.   탈출

탈출 시나리오1

 

탈출 시나리오2

이렇듯 열쇠1과 열쇠2를 얻는 순서는 바뀔 수 있다.
=> 위상정렬의 정답은 여러개일 수 있다!!
 
이러한 방문 순서를 결정하는 알고리즘을 알아보자.

---

위상정렬 알고리즘

위상정렬에는 진입차수를 저장하는 배열과 위상정렬의 정답을 저장하는 배열과 다음 정점을 기다리는 큐가 필요하다.
 
각 정점들의 진입차수(in-Degree)를 저장해야 한다. 진입차수란 자기 자신을 가리키는 엣지의 갯수를 의미한다.

위 그래프에서 정점 0의 진입차수는 0이고, 정점 5의 진입차수는 2이다.
 
모든 정점의 진입차수는 다음과 같다.

정점	0	1	2	3	4	5	6
진입차수	0	1	3	2	1	2	1

 
위상정렬의 동작
 1. 현재 진입차수가 0인 정점에 방문한다.
 2. 현재 정점이 가리키는 엣지의 정점들의 진입차수를 하나씩 낮춘다.
 3. 모든 정점을 방문할 때까지 1-2를 반복한다.
 
* 만약 그래프에 사이클이 있는 경우 사이클이 발생한 정점은 진입차수를 낮출 수 없어 위상정렬은 멈추게 된다.
 
 

---

동작 예시

 

정점	0	1	2	3	4	5	6
진입차수	0	0	3	2	0	2	1

 

=> 진입차수가 0인 정점 0에 방문
0이 가리키는 정점들인 1과 4의 진입차수가 1씩 낮아지고, 1과 4는 진입 차수가 0이므로 큐에 대기한다.

---

 

정점	0	1	2	3	4	5	6
진입차수	0	0	2	2	0	1	1

 

=>정점 1이 위상정렬 배열에 저장되고, 연결된 정점 2, 5의 진입차수를 낮춘다.

---

정점	0	1	2	3	4	5	6
진입차수	0	0	1	2	0	0	1

 

=> 정점 4가 배열에 저장되고, 연결된 정점 2, 5의 진입차수를 낮춘다.
정점 5가 진입차수가 0이 되어 큐에 추가된다.

---

정점	0	1	2	3	4	5	6
진입차수	0	0	0	2	0	0	1

 

=> 정점 5가 배열에 저장되고, 진입차수가 0이 된 정점 2가 큐에 추가된다.

---

정점	0	1	2	3	4	5	6
진입차수	0	0	0	1	0	0	0

=> 정점 2가 배열에 추가되고, 연결된 정점 6, 3의 진입차수가 낮아진다.
진입차수가 0이 된 정점 6이 큐에 추가된다.

---

정점	0	1	2	3	4	5	6
진입차수	0	0	0	0	0	0	0

정점 3이 마지막 노드이므로

 
위상정렬의 정답 배열은 위와 같이 채워지고 끝나게 된다.

---

위상정렬 cpp

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

int inDegree[7];			// 진입차수 저장
vector<int> v[7];			// 간선 정보 저장

void topologySort() {
	int result[7];			// 정답 배열
	queue<int> q;			// 큐
	for (int i = 0; i < 7; i++) {
		if (inDegree[i] == 0) q.push(i);		// 진입차수 0인 정점 큐에 푸쉬
	}
	for (int i = 0; i < 7; i++) {		// 정점의 갯수만큼 반복
		if (q.empty()) {				// 사이클 발생 체크
			cout << "사이클 발생\n";
			return;
		}
		int x = q.front();
		q.pop();
		result[i] = x;					// 정답 배열에 저장
		for (int j = 0; j < v[x].size(); j++) {
			int y = v[x][j];			// x가 가리키는 노드
			if (--inDegree[y] == 0) q.push(y);	// y의 진입차수를 낮추고, 만약 0이면 큐에 푸쉬
		}
	}

	for (int i = 0; i < 7; i++) {
		cout << result[i] << ' ';
	}
}

int main() {
	// 간선 및 진입차수 하드코딩
	v[0].push_back(1);
	inDegree[1]++;
	v[0].push_back(4);
	inDegree[4]++;
	v[1].push_back(2);
	inDegree[2]++;
	v[1].push_back(5);
	inDegree[5]++;
	v[4].push_back(2);
	inDegree[2]++;
	v[4].push_back(5);
	inDegree[5]++;
	v[5].push_back(2);
	inDegree[2]++;
	v[2].push_back(6);
	inDegree[6]++;
	v[2].push_back(3);
	inDegree[3]++;
	v[6].push_back(3);
	inDegree[3]++;

	topologySort();
	return 0;
}

//출력

 
예측했던 값과 동일한 정답이 나오는 것을 확인할 수 있다.

---

관련 문제

https://www.acmicpc.net/problem/14567
https://www.acmicpc.net/problem/2252
https://www.acmicpc.net/problem/1948