위상 정렬이란?
위상 정렬(Topological Sort)은 방향 그래프에서, 모든 간선 u→v에 대해 u가 v보다 앞에 오도록 정점을 한 줄로 세우는 것입니다. 선수과목 수강 순서, 작업 스케줄, 빌드 의존성처럼 "A를 끝내야 B를 할 수 있다"는 관계를 순서로 풀어낼 때 씁니다.
전제: 사이클이 없는 방향 그래프(DAG)여야 합니다. 사이클이 있으면 "A는 B보다 먼저, B는 A보다 먼저"가 동시에 요구돼 순서를 정할 수 없습니다.
핵심은 진입차수(in-degree)
진입차수는 "그 정점으로 들어오는 간선의 수" = "아직 끝나지 않은 선행 작업의 수"입니다.
진입차수가 0인 정점은 지금 당장 할 수 있는 작업입니다(선행이 없으므로). 그것을 처리하면 그 정점이 가리키던 다음 작업들의 선행이 하나 줄어듭니다. 이 아이디어가 Kahn 알고리즘입니다.
동작 원리 (Kahn 알고리즘)
1단계. 모든 정점의 진입차수를 계산합니다.
2단계. 진입차수가 0인 정점을 모두 큐에 넣습니다.
3단계. 큐에서 하나 꺼내 결과에 추가하고, 그 정점이 가리키는 인접 정점들의 진입차수를 1씩 줄입니다. 그 결과 0이 된 정점을 큐에 넣습니다.
4단계. 큐가 빌 때까지 반복합니다. 결과에 모든 정점이 담기면 성공, 결과 길이가 정점 수보다 작으면 사이클이 있다는 뜻입니다.
알고노트 시각화는 진입차수가 0이 되어 "준비됨" 상태가 되는 정점이 차례로 빠지는 과정을 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(V + E) |
| 공간 | O(V) |
모든 정점과 간선을 한 번씩 보므로 O(V + E)입니다.
예시로 따라가기
간선 A→B, A→C, B→D, C→D:
- •진입차수: A=0, B=1, C=1, D=2
- •A 처리 → B, C 진입차수 0 → 큐에
- •B 처리 → D=1, C 처리 → D=0 → 큐에
- •D 처리 → 결과
A, B, C, D(또는 A, C, B, D)
자주 하는 실수
- •사이클 미감지: 처리한 정점 수가 V보다 적으면 사이클입니다. 이 검사를 빼먹으면 잘못된 부분 결과를 답으로 냅니다.
- •유일성 착각: 위상 정렬 결과는 보통 여러 개입니다(진입차수 0이 여럿일 때). 문제가 사전순 등 특정 순서를 요구하면 우선순위 큐를 씁니다.
- •무방향 그래프 적용: 방향이 없으면 위상 정렬은 정의되지 않습니다.
알고노트에서 직접 확인하세요
진입차수가 0이 된 정점이 큐에 들어가고, 처리될 때마다 다음 정점들의 진입차수가 줄어드는 과정을 알고노트에서 단계별로 확인할 수 있습니다.