그래프의 노드를 정렬하는 위상정렬 정복하기

1. 개요 위상 정렬(topology sort)은 정렬 알고리즘의 일종 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 이론적으로, 위상 정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 실제 예를 들어 위상 정렬을 수행하는 전형적인 예시는, '선수과목을 고려한 학습 순서 결정'이 있다. 예를 들어 컴퓨터공학과 커리큘럼에는 '자료구조'과목을 수강한 뒤에, '알고리즘'강의를 수강하는 것을 권장한다. 이 경우에 자료구조와 알고리즘을 각각 노드로 표현하고, 자료구조에서 알고리즘으로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다. 그래프 상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순..