[정글 베이직 25] 위상 정렬(Topological Sort) 완전 정리

위상 정렬은 방향 그래프에서 "무엇을 먼저 해야 하는가"를 정하는 대표 알고리즘입니다. 선수 과목, 작업 순서, 빌드 순서, 업무 의존성 같은 문제에서 자주 등장합니다.

위상 정렬이란?

위상 정렬은 방향 그래프에서, 간선의 방향을 거스르지 않도록 정점을 순서대로 나열하는 것입니다.

쉽게 말하면 먼저 해야 하는 일을 먼저 배치하는 정렬입니다.

예시 1. 선수 과목

기초 과목을 먼저 듣고, 그 다음 중급 과목을 들어야 함

예시 2. 작업 순서

설계가 끝나야 구현을 시작할 수 있음

예시 3. 빌드 순서

라이브러리가 준비되어야 메인 프로젝트를 빌드 가능

핵심 개념: 진입 차수(in-degree)

진입 차수는 어떤 정점으로 들어오는 간선의 개수입니다.

A → B

이 경우 B는 A로부터 들어오는 간선 1개를 가지므로, B의 진입 차수는 1입니다.

즉, 진입 차수가 0인 정점은 "나보다 먼저 해야 할 것이 없는 정점"이므로 가장 먼저 처리할 수 있습니다.

문제 예제 시각화

문제의 예제를 선수 과목 관계로 해석해보면 다음과 같습니다.

0 (기초)

→

1 (중급)

→

3 (고급)

↘

2 (응용)

간선 의미

0 → 1 : 기초를 먼저 해야 중급 가능
0 → 2 : 기초를 먼저 해야 응용 가능
1 → 3 : 중급을 먼저 해야 고급 가능

정점	의미	초기 진입 차수	이유
0	기초	0	들어오는 간선이 없음
1	중급	1	0에서 1로 들어옴
2	응용	1	0에서 2로 들어옴
3	고급	1	1에서 3으로 들어옴

위상 정렬의 기본 아이디어

위상 정렬은 다음 흐름으로 진행합니다.

1단계

진입 차수가 0인 정점을 찾는다

→

2단계

그 정점을 결과에 넣는다

→

3단계

그 정점에서 나가는 간선을 제거한 것처럼 처리한다

→

4단계

새롭게 진입 차수 0이 된 정점을 다시 큐에 넣는다

큐 변화까지 포함한 단계별 시뮬레이션

초기 상태

진입 차수 배열: [0, 1, 1, 1]

진입 차수가 0인 정점: 0

큐: [0]

1단계: 0 처리

큐에서 0을 꺼내 결과에 추가합니다.

결과: [0]

0에서 나가는 간선은 0→1, 0→2 입니다.

따라서 1과 2의 진입 차수를 1씩 감소시킵니다.

진입 차수 변화: [0, 0, 0, 1]

새로 0이 된 정점 1, 2를 큐에 넣습니다. 큐: [1, 2]

2단계: 1 처리

큐에서 1을 꺼내 결과에 추가합니다.

결과: [0, 1]

1에서 나가는 간선은 1→3 입니다.

3의 진입 차수를 감소시킵니다.

진입 차수 변화: [0, 0, 0, 0]

이제 3도 큐에 들어갈 수 있습니다. 큐: [2, 3]

3단계: 2 처리

큐에서 2를 꺼내 결과에 추가합니다.

결과: [0, 1, 2]

2에서 나가는 간선은 없으므로 진입 차수 변화는 없습니다.

큐: [3]

4단계: 3 처리

큐에서 3을 꺼내 결과에 추가합니다.

결과: [0, 1, 2, 3]

큐가 비었으므로 종료합니다.

한눈에 보는 진행 표

단계	큐에서 꺼낸 정점	결과 리스트	변경 후 큐	진입 차수
초기	-	[]	[0]	[0, 1, 1, 1]
1	0	[0]	[1, 2]	[0, 0, 0, 1]
2	1	[0, 1]	[2, 3]	[0, 0, 0, 0]
3	2	[0, 1, 2]	[3]	[0, 0, 0, 0]
4	3	[0, 1, 2, 3]	[]	[0, 0, 0, 0]

왜 정답이 여러 개일 수 있을까?

위상 정렬은 조건만 만족하면 여러 정답이 가능합니다.

정답 예시 1

[0, 1, 2, 3]

정답 예시 2

[0, 2, 1, 3]

그 이유는 0을 처리한 뒤에는 1과 2가 모두 진입 차수 0이 되기 때문입니다. 즉, 둘 다 바로 처리할 수 있으므로 어떤 것을 먼저 꺼내느냐에 따라 결과가 달라질 수 있습니다.

사이클이 있으면 어떻게 될까?

위상 정렬은 사이클이 없는 방향 그래프(DAG)에서만 가능합니다.

0 → 1
1 → 2
2 → 0

이런 구조는 서로가 서로를 기다리는 상태라서, 진입 차수가 0인 정점이 생기지 않습니다. 따라서 위상 정렬을 끝까지 만들 수 없습니다.

풀이 핵심 정리

Kahn 알고리즘의 핵심은 딱 3가지입니다.

1. 그래프와 진입 차수 배열을 만든다.

2. 진입 차수가 0인 정점을 큐에 넣는다.

3. 큐에서 꺼내면서 연결된 정점의 진입 차수를 줄이고, 새롭게 0이 되면 큐에 넣는다.

정답 코드

from collections import deque

def topological_sort(vertices, edges):
    """
    위상 정렬 (Kahn's Algorithm)
    """
    graph = [[] for _ in range(vertices)]
    in_degree = [0] * vertices

    # 그래프 구성 및 진입 차수 계산
    for a, b in edges:
        graph[a].append(b)
        in_degree[b] += 1

    # 진입 차수가 0인 정점들을 큐에 추가
    queue = deque()
    for i in range(vertices):
        if in_degree[i] == 0:
            queue.append(i)

    result = []

    # 큐가 빌 때까지 반복
    while queue:
        node = queue.popleft()
        result.append(node)

        for next_node in graph[node]:
            in_degree[next_node] -= 1
            if in_degree[next_node] == 0:
                queue.append(next_node)

    return result

# 테스트 케이스
if __name__ == "__main__":
    vertices = 4
    edges = [
        (0, 1),  # 0 → 1
        (0, 2),  # 0 → 2
        (1, 3),  # 1 → 3
    ]

    print("=== 위상 정렬 ===")
    print("과목 관계:")
    print("  0(기초) → 1(중급) → 3(고급)")
    print("  0(기초) → 2(응용)")
    print()

    result = topological_sort(vertices, edges)
    print(f"수강 순서: {result}")

한 줄 요약

위상 정렬은 진입 차수가 0인 정점부터 꺼내며 순서를 만드는 알고리즘입니다. 그리고 여러 정점이 동시에 0이 되면 정답은 여러 개가 될 수 있습니다.