위상 정렬(Topological Sort) 완벽 이해: 개념, 구현, 사이클 판별까지 한 번에 정리

**위상 정렬(Topological Sort)**은 방향 그래프(DAG: Directed Acyclic Graph)의 정점들을 선후 관계에 맞춰 순서대로 나열하는 알고리즘입니다.
선수 과목 → 후수 과목, 작업 순서 지정, 빌드 순서 등 순차적 의존성을 가지는 문제에서 자주 활용됩니다.

이번 글에서는 위상 정렬의 개념, 구현 방식(Kahn 알고리즘 / DFS 기반), 사이클 판별, 실전 예제까지 완벽하게 정리합니다.

✅ 위상 정렬(Topological Sort)이란?

방향성이 있는 그래프(DAG)에서,
"A → B"라면 A를 B보다 먼저 나열하는 방식으로 모든 정점을 정렬

🔹 위상 정렬의 전제 조건

사이클이 없어야 한다 (Acyclic)
반드시 **유향 그래프(Directed Graph)**여야 한다
모든 노드를 정렬하지 못한다면 → 사이클 존재

🧠 실전 예시

과목 이수 순서
프로젝트 빌드 순서
작업 스케줄링
패키지 의존성 순서

📌 방법 1: Kahn's Algorithm (Queue 기반)

진입차수(in-degree)가 0인 노드를 큐에 삽입
큐에서 노드를 꺼내 정렬 리스트에 추가
해당 노드와 연결된 노드의 진입차수 1 감소
진입차수가 0이 되면 다시 큐에 삽입
모든 노드를 처리할 때까지 반복

🧪 Python 구현 (Kahn 알고리즘)

from collections import deque

def topological_sort(V, edges):
    graph = [[] for _ in range(V)]
    indegree = [0] * V

    # 그래프 및 진입차수 초기화
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(V) if indegree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

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

    if len(result) != V:
        return "사이클 존재 (위상 정렬 불가)"
    return result

edges = [(0, 2), (1, 2), (2, 3), (3, 4)]
print(topological_sort(5, edges))  # 출력: [0, 1, 2, 3, 4]

📌 방법 2: DFS 기반 위상 정렬

DFS 탐색 종료 후 역순으로 노드를 스택에 저장

def dfs_topo_sort(V, edges):
    graph = [[] for _ in range(V)]
    for u, v in edges:
        graph[u].append(v)

    visited = [False] * V
    result = []

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        result.append(node)  # 후위 순회

    for i in range(V):
        if not visited[i]:
            dfs(i)

    return result[::-1]  # 역순 반환

edges = [(0, 2), (1, 2), (2, 3), (3, 4)]
print(dfs_topo_sort(5, edges))  # 출력: [1, 0, 2, 3, 4]

⚠️ 사이클 판별

Kahn 알고리즘: 결과 리스트의 길이 ≠ V → 사이클 존재
DFS 방식: 탐색 중 visited + recursion stack에 같은 노드 감지 → 사이클 존재

def has_cycle(V, edges):
    graph = [[] for _ in range(V)]
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * V  # 0: 미방문, 1: 방문중, 2: 방문완료

    def dfs(node):
        if visited[node] == 1:
            return True  # 사이클 존재
        if visited[node] == 2:
            return False

        visited[node] = 1
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        visited[node] = 2
        return False

    for i in range(V):
        if dfs(i):
            return True
    return False

🎯 실전 활용 문제 유형

문제 유형 설명

과목 순서 정하기	선수 과목이 있는 과목들을 올바른 순서로 나열
작업 우선순위	이전 작업이 끝나야 시작할 수 있는 작업 나열
빌드 순서	라이브러리 또는 패키지 의존성 해결 순서
DAG의 사이클 판별	위상 정렬 불가능 시 → 순환 의존 확인

📌 결론 및 요약

위상 정렬은 DAG에서 선행 관계를 가진 작업을 순서대로 나열할 때 사용
Kahn 알고리즘은 진입차수 기반, DFS 방식은 후위 탐색 기반
사이클이 존재하면 위상 정렬 불가, 이를 판별하는 데도 활용 가능

👉 다음 글에서는 유니온 파인드(Union-Find) 자료구조를 기반으로
사이클 판별, 네트워크 그룹화, 최소 신장 트리 연결 등 실전 응용을 알아봅니다.

📚 참고자료 및 출처

『이것이 취업을 위한 코딩 테스트다 with Python』
백준 2252(줄 세우기), 1516(게임 개발), 2637(장난감 조립)
GeeksforGeeks – Topological Sort

위상정렬, topological sort, kahn algorithm, dfs 위상정렬, 사이클 탐지, DAG, 작업순서, 파이썬 그래프, 코딩테스트 준비, SEO 최적화 10개