한양과기고 에듀테크 수업도구 대시보드

위상 정렬 (Topological Sort)

"A를 하기 전에 B를 먼저 끝내야 한다" 같은 선후 관계가 있는 일들을, 규칙을 하나도 어기지 않는 순서로 한 줄로 세우는 것이 위상 정렬이다. 선수과목 이수 순서, 빌드 시스템의 컴파일 순서, 엑셀 수식 재계산 순서가 모두 같은 문제다. 관계를 방향 그래프(DAG) 로 그리면, 화살표를 거스르지 않는 일렬 나열을 찾는 일이 된다. 단, 그래프에 사이클이 있으면 (서로가 서로의 선행 조건) 그런 순서는 존재하지 않는다.

Kahn 알고리즘 시뮬레이터 — 선수과목 이수 순서

큐 (진입차수 0 = 지금 들을 수 있는 과목)

확정된 이수 순서

다음 단계 를 눌러 보세요. 각 노드 옆 숫자는 진입차수(아직 남은 선행 과목 수)입니다. 진입차수가 0 이 된 과목은 큐에 들어가 수강 가능해집니다.

Kahn 알고리즘 (BFS / 진입차수 방식)

from collections import deque

def topological_sort(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:          # u를 끝내야 v를 할 수 있다
        adj[u].append(v)
        indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()             # 선행 조건이 모두 끝난 일
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1          # 선행 하나 해결
            if indeg[v] == 0:
                q.append(v)

    if len(order) != n:
        raise ValueError("사이클이 있어 위상 정렬 불가")
    return order

진입차수(in-degree) = 그 노드로 들어오는 화살표 수 = 아직 안 끝난 선행 작업 수. 0이면 지금 바로 할 수 있다.
일을 하나 끝낼 때마다 그 일에 의존하던 노드들의 진입차수를 1씩 줄이고, 0이 되면 큐에 넣는다.
큐가 비었는데 len(order) < n 이면 → 남은 노드들이 서로 순환 의존. 위상 정렬이 존재하지 않는다 (사이클 감지).
시간 복잡도 O(V + E) — 노드와 간선을 각각 한 번씩만 본다.
큐에서 어떤 노드를 먼저 꺼내느냐에 따라 정답이 여러 개일 수 있다 (우선순위 큐를 쓰면 사전순 최소 순서).

DFS 방식 & 어디에 쓰나

DFS 방식: 각 노드에서 DFS를 돌다가 돌아 나올 때(post-order) 스택에 push. 마지막에 스택을 거꾸로 읽으면 위상 순서. DFS 중 회색(방문 중) 노드로 되돌아가는 간선을 만나면 사이클.
빌드 시스템 (Make, Gradle, Bazel): 소스 → 오브젝트 → 실행파일 의존 그래프를 위상 정렬해 컴파일 순서 결정, 독립적인 부분은 병렬 빌드.
패키지 매니저 (npm, pip, apt): 패키지 의존성을 풀어 설치 순서 결정. 순환 의존이면 오류.
스프레드시트: C1 = A1 + B1 처럼 셀 참조 그래프를 위상 정렬해 재계산 순서 결정. 순환 참조 경고가 바로 이 사이클 감지.
작업 스케줄러 · 강의 계획 · 게임 기술 트리: 선행 조건이 있는 태스크 나열.

방식	자료구조	사이클 감지	비고
Kahn (BFS)	큐 + 진입차수	order 길이 < n	직관적, 병렬화 쉬움
DFS post-order	재귀 스택	back edge(회색 노드)	코드 짧음