위상정렬 (Topological Sort) 완벽 정리

위상정렬 (Topological Sort) 완벽 정리

✅ 위상정렬이란?

방향 그래프(DAG)에서 선행 조건을 지키며 노드들을 정렬하는 알고리즘.

대표적인 예:

• 선수과목 → 후속 과목
• 작업 A → 작업 B (A를 먼저 해야 B가 가능)

---

🔑 조건

• DAG (Directed Acyclic Graph) 이어야 함
• 사이클이 존재하면 위상정렬 불가능

---

📘 용어 정리

용어	의미
진입 차수	해당 노드로 들어오는 간선의 개수
진출 차수	해당 노드에서 나가는 간선의 개수
진입 차수 0	선행 조건이 없는 노드, 바로 처리 가능

---

🔁 위상정렬 알고리즘 흐름 (진입 차수 기반)

1. 모든 노드의 진입 차수 계산
2. 진입 차수가 0인 노드를 큐에 삽입
3. 큐에서 꺼내며 결과 리스트에 추가
4. 꺼낸 노드가 향하는 노드들의 진입 차수 -1
5. 새로 진입 차수 0이 된 노드를 큐에 삽입
6. 큐가 빌 때까지 반복

---

🔍 예시

입력:

4 2 1 2 3 2

그래프:

1 → 2 ← 3

초기 진입 차수:

• 1: 0
• 2: 2
• 3: 0
• 4: 0

정렬 결과 예:

1 3 4 2 또는 3 1 4 2 (2는 반드시 마지막)

---

💻 파이썬 코드 (백준 2252번 기준)

from collections import deque

n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

q = deque()
for i in range(1, n + 1):
    if indegree[i] == 0:
        q.append(i)

result = []

while q:
    now = q.popleft()
    result.append(now)
    for nxt in graph[now]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            q.append(nxt)

print(*result)

---

📌 정리

• 위상정렬은 순서를 지켜야 할 작업들을 처리할 때 매우 유용
• 진입 차수 0인 노드를 시작점으로, 순서를 확정시켜나감
• 사이클이 있으면 정렬할 수 없음 (진입 차수가 0인 노드가 사라지지 않음)

---

🧠 함께 보면 좋은 백준 문제

문제 번호 제목 설명

2252	줄 세우기	위상정렬 기본 문제
1516	게임 개발	위상정렬 + DP
2056	작업	위상정렬 + DP (구조 유사)
2623	음악프로그램	위상정렬 + 여러 조건 처리