Ch.7 그래프
위상정렬 — 선수과목부터 들어라!
선수과목을 안 들으면 수강신청이 안 된다
대학 수강신청을 해본 적 있나요? 미적분을 들으려면 먼저 수학1을, 수학1을 들으려면 기초수학을 들어야 합니다. 이 순서를 정하는 것이 위상정렬입니다.
만약 A→B→C→A 같은 순환이 있으면? 어떤 과목부터 들어야 하지?
사이클이 있으면 위상정렬이 불가능합니다. 이것이 바로 'Course Schedule' 문제의 핵심입니다.
핵심 개념
위상정렬(Topological Sort)
방향 그래프에서 선행 조건을 만족하는 순서
진입차수(In-degree)
한 노드로 들어오는 엣지의 수
핵심 내용
순서가 있는 작업을 정렬하는 위상정렬을 배웁니다
진입차수가 0인 노드 = 선행 조건이 없는 노드. 이 노드부터 처리를 시작합니다
위상정렬은 DAG(사이클 없는 방향 그래프)에서만 가능합니다. 사이클이 있으면 정렬 불가!
Kahn's Algorithm은 BFS + 진입차수로 위상정렬을 구현합니다
from collections import deque, defaultdict
def topological_sort(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
# 진입차수 0인 노드부터 시작
queue = deque()
for i in range(numCourses):
if in_degree[i] == 0:
queue.append(i)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 모든 노드를 처리했는지 확인 (사이클 체크)
return order if len(order) == numCourses else []Kahn's Algorithm 3단계 1. 진입차수 계산 + 진입차수 0인 노드를 큐에 넣기 2. 큐에서 꺼내며 이웃의 진입차수 감소 → 0이 되면 큐에 추가 3. 처리된 노드 수 ≠ 전체 노드 수 → 사이클 존재
마지막 줄 `len(order) == numCourses`가 사이클 감지 핵심입니다. 사이클 안의 노드는 진입차수가 0이 되지 않습니다!
3개 과목의 위상정렬을 단계별로 추적합니다
결과: [0, 1, 2] 선수과목 순서대로 완벽하게 정렬되었습니다
면접 단골 문제! 모든 과목을 수강할 수 있는가?
# LeetCode 207: Course Schedule
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for crs, pre in prerequisites:
graph[pre].append(crs)
in_degree[crs] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0
while queue:
node = queue.popleft()
count += 1
for nb in graph[node]:
in_degree[nb] -= 1
if in_degree[nb] == 0:
queue.append(nb)
return count == numCourses # True면 사이클 없음 → 수강 가능
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (사이클!)Course Schedule = 사이클 감지 문제. 위상정렬로 모든 노드를 처리할 수 있으면 사이클 없음!
위상정렬에서 가장 먼저 큐에 들어가는 노드의 진입차수는?
사이클이 있는 방향 그래프에서도 위상정렬이 가능하다
위상정렬 마스터!
핵심 용어
위상정렬
선행 조건을 지키면서 모든 노드를 나열
진입차수
노드로 들어오는 엣지 수 — 0이면 시작 가능
DAG
Directed Acyclic Graph — 위상정렬의 전제 조건
정리 노트
위상정렬 & Kahn's Algorithm
핵심 알고리즘
- Kahn's
- 진입차수 0인 노드부터 BFS → 이웃 진입차수 감소
- 사이클 감지
- `len(order) != numCourses` → 사이클 존재
- 시간 복잡도
- O(V + E)
면접 포인트
- Course Schedule
- 위상정렬 → 모든 노드 처리 가능? → 사이클 체크
- DAG 전제
- 위상정렬은 사이클 없는 방향 그래프에서만 가능
위상정렬 = BFS + 진입차수. 'count == numCourses'로 사이클 판별!
시각 자료
핵심 정리
- 1위상정렬 = 선행 조건을 지키며 모든 노드 정렬
- 2Kahn's Algorithm: 진입차수 0 → BFS → 진입차수 감소
- 3Course Schedule = 사이클 감지 문제
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작