위상 정렬 #Topological Sort [ 수정 내역 ] [ 수정 ]

최근 수정: 6년 전

1. 개요

Topological Sort.

DAG에서 순서를 찾는 알고리즘.

일반적인 정렬인 버블 소트, 퀵 소트[1] 등과는 다르다.

2. 예시

게임에서의 스킬 트리를 생각하면 된다. 예를 들어 B 스킬을 찍기 위해서는 A 스킬을 찍어야 한다거나 C 스킬을 찍기 위해서는 B 스킬을 찍어야 할 때, 스킬 트리는 DAG 형태이며, 여기서 스킬을 찍는 순서(A, B, C)를 구하려면 위상 정렬을 하면 된다.

3. 구현

그래프의 indegree[2]가 0이 되는 노드는 바로 시작할 수 있다는 점이 중요!

BFS처럼 indegree가 0이 되는 노드들을 큐에 넣으면서 탐색하면 된다.

[1] 정렬 문서 참고.

[2] 들어오는 간선의 수. 자세한 건 그래프 문서 참고.