5. 위상 정렬

컴퓨터공학 수업을 들으려면 먼저 자료구조를 들어야 하고, 자료구조 전에는 프로그래밍 입문을 들어야 합니다. 이렇게 "A를 하기 전에 B를 반드시 끝내야 한다"는 선후 관계가 얽혀 있을 때, 모순 없이 순서를 한 줄로 세우는 것이 위상 정렬(Topological Sort)입니다. 선수과목 짜기, 빌드 의존성 해결, 요리 순서 정하기가 전부 같은 문제예요.

좋은 소식: 여러분은 이미 BFS와 deque를 배웠습니다. 위상 정렬은 사실상 BFS 큐 패턴의 응용이라서, 새 무기를 배우기보다 있던 무기를 새 문제에 겨누는 챕터입니다.

이 한 챕터에서 배우는 것:

선후 관계를 방향 그래프(DAG) 로 표현하는 법
진입차수(in-degree) 개념과 "지금 당장 할 수 있는 일" 찾기
큐 기반 카안 알고리즘(Kahn's Algorithm) 완성 구현
사이클(순환 의존성)을 감지해서 "순서를 못 정한다"고 판단하는 법

문제를 그림으로: 방향 그래프(DAG)

"B를 하려면 A가 먼저"라는 관계를 화살표 A → B로 그립니다. 화살표에 방향이 있으니 방향 그래프고, 이런 선후 관계엔 돌고 도는 사이클이 없어야 말이 됩니다(A 전에 B, B 전에 A는 불가능). 사이클이 없는 방향 그래프를 DAG(Directed Acyclic Graph) 라고 불러요.

예를 들어 요리 순서가 이렇다고 합시다.

재료손질을 먼저 해야 볶기와 끓이기를 할 수 있고, 둘 다 끝나야 간맞추기가 가능합니다. 가능한 순서 하나는 재료손질 → 볶기 → 끓이기 → 간맞추기 예요. (볶기와 끓이기는 서로 순서를 바꿔도 됩니다. 위상 정렬의 답은 여러 개일 수 있어요.)

핵심 도구: 진입차수(in-degree)

어떤 작업을 지금 당장 시작할 수 있는지는 어떻게 알까요? "나에게 들어오는 화살표가 하나도 없으면" 됩니다. 즉 나보다 먼저 끝내야 할 선행 작업이 없다는 뜻이니까요.

각 노드로 들어오는 화살표의 개수를 진입차수(in-degree) 라고 합니다. 위 그림에서:

작업	진입차수	의미
재료손질	0	선행 작업 없음, 바로 시작 가능
볶기	1	재료손질을 기다림
끓이기	1	재료손질을 기다림
간맞추기	2	볶기와 끓이기 둘 다 기다림

💡 위상 정렬의 전부는 이 한 문장입니다. "진입차수가 0인 것부터 처리하고, 처리하면서 그 뒤에 딸린 작업들의 진입차수를 1씩 깎는다." 깎다 보면 또 0이 되는 작업이 생기고, 그게 다음 차례예요.

카안 알고리즘: BFS 큐 패턴으로 순서 뽑기

절차를 정리하면 이렇습니다. BFS에서 큐에 넣고 빼며 처리하던 그 리듬 그대로예요.

모든 노드의 진입차수를 계산한다.
진입차수가 0인 노드를 전부 큐(deque)에 넣는다.
큐에서 하나 꺼내 결과에 기록한다.
그 노드가 가리키던 이웃들의 진입차수를 1씩 깎고, 0이 되면 큐에 넣는다.
큐가 빌 때까지 3~4를 반복한다.

먼저 그래프를 인접 리스트로 표현하고, 진입차수 배열을 만듭니다.

from collections import deque

# graph[u] = u가 가리키는(먼저 끝나야 u 다음에 할 수 있는) 노드들
graph = {
    "재료손질": ["볶기", "끓이기"],
    "볶기": ["간맞추기"],
    "끓이기": ["간맞추기"],
    "간맞추기": [],
}

def topo_sort(graph):
    # 1) 진입차수 계산: 일단 모두 0으로 두고, 화살표가 도착할 때마다 +1
    in_degree = {node: 0 for node in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    # 2) 진입차수 0인 노드부터 큐에 (BFS 시작점 여러 개인 셈)
    queue = deque(node for node in graph if in_degree[node] == 0)

    result = []
    while queue:
        u = queue.popleft()     # 3) 큐에서 꺼내 결과에 기록
        result.append(u)
        for v in graph[u]:      # 4) u 뒤에 딸린 이웃들의 진입차수를 깎기
            in_degree[v] -= 1
            if in_degree[v] == 0:   # 선행 작업이 다 끝났으면 이제 시작 가능
                queue.append(v)

    return result

print(topo_sort(graph))
# ['재료손질', '볶기', '끓이기', '간맞추기']

재료손질만 진입차수 0이라 처음 큐에 들어가고, 이걸 꺼내면서 볶기·끓이기의 진입차수가 0이 되어 큐에 합류합니다. 딕셔너리 삽입 순서 덕분에 볶기가 먼저 나오지만, 정답은 여러 개라는 점을 기억하세요.

💡 popleft()(앞에서 꺼내기) + append()(뒤에 넣기)로 먼저 준비된 것부터 처리하는 이 흐름이 바로 BFS입니다. 위상 정렬은 "시작점이 여러 개이고, 이웃을 큐에 넣는 조건이 '진입차수 0'인 BFS"라고 이해하면 딱 맞아요.

사이클 감지: 순서를 못 정하는 경우

만약 A → B, B → C, C → A처럼 돌고 돌면 어떻게 될까요? 세 노드 모두 진입차수가 1이라 애초에 큐에 넣을 시작점(진입차수 0)이 없습니다. 큐가 비어 있으니 while 루프는 한 번도 못 돌고, 결과에 아무도 담기지 않아요.

핵심 판별법: 결과에 담긴 노드 개수가 전체 노드 개수보다 적으면, 사이클이 존재하는 것입니다.

from collections import deque

def topo_sort(graph):
    in_degree = {node: 0 for node in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque(node for node in graph if in_degree[node] == 0)
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(result) != len(graph):   # 다 못 담았으면 사이클!
        return None                 # 위상 정렬 불가
    return result

cyclic = {"A": ["B"], "B": ["C"], "C": ["A"]}
print(topo_sort(cyclic))
# None

ok = {"A": ["B"], "B": ["C"], "C": []}
print(topo_sort(ok))
# ['A', 'B', 'C']

💡 사이클이 있으면 그 안의 노드들은 진입차수가 절대 0으로 떨어지지 않아 큐에 못 들어갑니다. 그래서 len(result) < len(graph) 한 줄로 순환 의존성을 잡아낼 수 있어요. 빌드 도구가 "circular dependency" 에러를 뱉는 게 바로 이 검사입니다.

시간복잡도

카안 알고리즘은 모든 노드를 한 번씩 큐에서 꺼내고(V번), 각 노드의 모든 화살표를 한 번씩 따라가며 진입차수를 깎습니다(총 E번). 그래서 시간복잡도는 O(V + E) 예요. (V = 노드 수, E = 간선 수)

노드와 간선을 딱 한 번씩만 훑으니 아주 빠릅니다. 노드가 10만 개, 간선이 20만 개여도 약 30만 번이라 1초 안에 여유 있게 끝나요. BFS와 완전히 같은 O(V + E) 라는 점도 "위상 정렬 = BFS 응용"을 뒷받침합니다.

정리

개념	한 줄 요약
DAG	방향이 있고 사이클이 없는 그래프. 선후 관계 표현용
진입차수(in-degree)	나에게 들어오는 화살표 수. 0이면 지금 시작 가능
카안 알고리즘	진입차수 0을 큐에 넣고 BFS로 빼면서 이웃 진입차수 깎기
사이클 감지	결과 개수 < 전체 노드 수 이면 순환 의존성 존재
시간복잡도	O(V + E), BFS와 동일

💡 위상 정렬 문제인지 알아보는 신호: "~하기 전에 ~를 먼저", "선수", "의존성", "순서를 정하라" 라는 말이 나오면 화살표를 그리고 진입차수를 세보세요. 그다음은 늘 똑같은 카안 템플릿입니다.

직접 풀어보기

위 topo_sort에 선수과목 그래프 {"프로그래밍입문": ["자료구조"], "자료구조": ["알고리즘"], "알고리즘": []} 를 넣고 결과를 확인해보세요. (정답: ['프로그래밍입문', '자료구조', '알고리즘'])
결과를 담을 때 큐에 들어간 순서 대신 사전순으로 뽑고 싶다면 어떻게 할까요? (힌트: deque 대신 heapq(최소 힙)를 쓰면 항상 가장 작은 것부터 꺼낼 수 있습니다.)
노드 A, B, C, D에 대해 A → B, B → C, C → D, D → B 관계를 딕셔너리로 만들고 topo_sort를 돌려보세요. None이 나오는 이유를 진입차수로 설명해보세요. (힌트: B, C, D가 사이클을 이룹니다.)