위상 정렬(Topological Sort)
위상 정렬(Topological Sort)은 사이클이 없는 방향 그래프(DAG)에서 노드의 선후 관계를 파악하여 순서를 정하는 알고리즘입니다. 선수과목이 있는 대학 강의의 수강 순서를 정하거나, 의존성을 가지는 작업들의 실행 순서를 정하는 데 사용됩니다.
1. '위상'은 무슨 뜻일까? 💡
위상 정렬에서 '위상(Topology)'이란, 그래프의 '변치 않는 본질적인 구조와 순서'를 의미합니다.
그래프의 노드 위치를 바꾸거나 간선(edge)을 고무줄처럼 늘여도, '어떤 노드가 특정 노드보다 반드시 먼저 와야 한다'는 선후 관계(dependency) 자체는 절대 변하지 않습니다. 이 근본적인 연결 관계가 바로 그래프의 '위상'입니다.
따라서 위상 정렬이란, 이 변치 않는 순서 관계를 존중하여 모든 노드를 모순이 없는 하나의 줄로 나열하는 것을 의미합니다.
지하철 노선도 🚇 비유는 이 개념을 이해하는 가장 좋은 방법입니다. 노선도는 실제 역간 거리를 무시하고 오직 '역들의 순서'와 '환승 관계'라는 위상 정보만을 보여줍니다. 이 노선에서 한 방향으로만 이동하며 역 이름을 순서대로 부르는 것이 바로 위상 정렬의 결과와 같습니다.
2. 주요 특징
- 결과는 유일하지 않을 수 있습니다.
- 시작할 수 있는 노드(진입 차수가 0인 노드)가 여러 개라면 다양한 결과가 나올 수 있습니다.
- 사이클이 존재하면 안 됩니다.
- 노드 간의 순서를 명확히 정의할 수 없으므로 위상 정렬을 적용할 수 없습니다.
3. 알고리즘 과정
-
그래프 표현
- 입력 정보를 바탕으로 인접 리스트를 만듭니다.
-
진입 차수 계산
- 각 노드(Node)를 기준으로, 해당 노드로 들어오는 간선(Edge)의 개수인 진입 차수(In-degree)를 계산하여 리스트에 저장합니다.
-
큐(Queue)를 이용한 정렬
- 진입 차수가 0인 모든 노드를 큐에 넣습니다.
- 큐가 빌 때까지 다음을 반복합니다.
- 큐에서 노드를 하나 꺼내 결과에 추가합니다.
- 꺼낸 노드에서 출발하는 모든 간선을 따라가며, 연결되어 있던 노드들의 진입 차수를 1씩 감소시킵니다.
- 이때, 진입 차수가 새로 0이 된 노드가 있다면 즉시 큐에 추가합니다.
4. 사이클과 위상 정렬
만약 그래프에 사이클(Cycle)이 존재하면, 사이클에 포함된 노드들은 서로가 먼저 처리되기를 기다리는 교착 상태에 빠집니다.
결과적으로, 이 노드들의 진입 차수는 절대 0이 될 수 없으므로 큐에 들어가지 못합니다. 따라서 위상 정렬이 모든 노드를 처리하지 못하고 종료되며, 이를 통해 사이클의 존재를 판별할 수도 있습니다.
5. Python 구현 예제 (BOJ 2252번: 줄 세우기)
이 문제에 위상 정렬을 사용하는 이유
"학생 A가 학생 B보다 앞에 서야 한다"는 조건은 명확한 '방향성'과 '선후 관계'를 가집니다.
- 학생 → 노드(Node)
- "A가 B 앞에 선다" → 방향 간선(A → B)
이렇게 문제를 그래프로 모델링하면, 학생들을 줄 세우는 것은 결국 '선후 관계를 모두 만족시키면서 모든 노드를 순서대로 나열하는 것'과 같습니다. 이는 정확히 위상 정렬 알고리즘이 해결하고자 하는 문제입니다.
"내 앞에 서야 할 사람이 모두 섰을 때" 비로소 내가 줄을 설 수 있다는 논리가 진입 차수가 0이 될 때 큐에 들어가는 과정과 완벽하게 일치하기 때문입니다.
import sys
from collections import deque
# N: 학생 수 (노드), M: 키 비교 횟수 (간선)
N, M = map(int, sys.stdin.readline().split())
# 1. 그래프 및 진입 차수 리스트 초기화
# 인접 리스트: lst[A]는 A 학생 바로 뒤에 올 수 있는 학생들의 목록
lst = [[] for _ in range(N + 1)]
# 진입 차수 리스트: degree[B]는 B 학생 앞에 서야 하는 학생의 수
degree = [0] * (N + 1)
# 2. 그래프 정보 입력 및 진입 차수 계산
# M번의 비교 정보를 바탕으로 그래프를 구성합니다.
for _ in range(M):
A, B = map(int, sys.stdin.readline().split())
# A가 B 앞에 서므로, A -> B 방향의 간선으로 표현
lst[A].append(B)
# B의 진입 차수(앞에 서야 할 학생 수) 1 증가
degree[B] += 1
# 3. 위상 정렬 실행
# 알고리즘에 사용할 큐 생성
que = deque()
# 맨 앞에 설 수 있는 학생(진입 차수가 0인 학생)을 모두 큐에 추가
for i in range(1, N + 1):
if degree[i] == 0:
que.append(i)
# 큐가 빌 때까지, 즉 모든 학생을 줄 세울 때까지 반복
while que:
# 현재 줄을 설 학생을 큐에서 꺼냄
now = que.popleft()
# 해당 학생을 줄에 세움 (결과 출력)
print(now, end=" ")
# 현재 줄 선 학생(now)의 뒤에 서야 하는 학생(next)들을 확인
for next_node in lst[now]:
# 'now'가 줄을 섰으므로, 'next_node'의 진입 차수를 1 감소
degree[next_node] -= 1
# 만약 'next_node' 앞에 서야 할 학생들이 모두 줄을 섰다면 (진입 차수가 0이 되면)
if degree[next_node] == 0:
# 'next_node'도 이제 줄을 설 수 있으므로 큐에 추가
que.append(next_node)