위상정렬

위상정렬(Topological Sort)은 의존성이 있는 작업들이 주어질 때

이들을 어떤 순서로 수행해야 하는 지를 순서대로 나열하는 것을 의미합니다.

사용법의 예로 대학의 선수과목 구조에서 특정 수강과목에 선수과목이 있다면 선수과목을 먼저 수강해야 하므로

선후관계가 있는 이 구조를 그래프로 만들어 위상정렬하게 된다면 올바른 수강 순서를 찾을 수 있습니다.

위상정렬이 가능하려면 유향그래프(Directed Graph)에 순환(cycle)이 존재하지 않아야하며

이는 DAG(Directed Acylic Graph)여야 한다는 것을 알 수 있습니다.

위상정렬은 아래의 2가지 방법을 사용하여 구할 수 있습니다.

1. DFS의 종료하는 순서를 기록한 뒤 뒤집는다.

2. 들어오는 간선이 없는 정점을 큐에 넣은 뒤 큐에서 하나를 빼고 그 정점에서 나가는 간선을 지우는 과정을 반복한다.

두 방법 모두 간단하며 둘 중 자신에게 좀 더 편한 방법으로 구현할 수 있습니다.

위상정렬을 하면서 또는 정렬의 결과 값을 응용하여 문제를 풀 수 있는 경우의 유형도 있으니

자신이 사용하는 방법을 원리를 확실하게 이해해두는 것이 좋습니다.

기본 문제

2252번: 줄 세우기

1766번: 문제집

1005번: ACM Craft