위상 정렬 작업 스케줄링 완벽 가이드

소프트웨어 개발이나 복잡한 프로젝트 매니지먼트를 수행하다 보면, 특정 작업을 시작하기 전에 반드시 선행되어야 하는 작업들이 존재합니다. 대학교 전공 과목의 선수 과목 이수 체계나 안드로이드 빌드 시스템의 의존성 관리 등이 대표적인 사례입니다. 이러한 '순서가 정해진 작업'을 논리적으로 나열하기 위해 필수적인 자료구조 알고리즘이 바로 위상 정렬(Topological Sort)입니다. 본 포스팅에서는 기술적 깊이를 더해 위상 정렬의 개념부터 구현 방법, 그리고 실무 적용 시 주의사항까지 심도 있게 다루어 보겠습니다.

1. 위상 정렬(Topological Sort)의 정의와 성립 조건

위상 정렬은 방향 그래프의 모든 노드를 방향성에 어긋나지 않도록 순서대로 나열하는 것을 의미합니다. 하지만 모든 방향 그래프에서 위상 정렬이 가능한 것은 아닙니다. 위상 정렬이 성립하기 위해서는 반드시 DAG(Directed Acyclic Graph), 즉 '사이클이 없는 방향 그래프'여야만 합니다. 만약 그래프 내에 사이클이 존재한다면, 어떤 작업이 먼저 시작되어야 하는지 결정할 수 없는 모순에 빠지게 되며, 이는 논리적 교착 상태를 유발합니다.

1-1. 진입 차수(In-degree)의 이해

위상 정렬 알고리즘을 이해하기 위한 가장 핵심적인 용어는 진입 차수(In-degree)입니다. 진입 차수란 특정한 노드로 들어오는 간선의 개수를 의미합니다. 위상 정렬의 관점에서 특정 노드의 진입 차수가 0이라는 것은 해당 작업을 시작하기 위해 먼저 처리해야 할 선행 작업이 더 이상 없다는 것을 뜻합니다. 따라서 모든 위상 정렬 알고리즘은 항상 진입 차수가 0인 노드부터 탐색을 시작하게 됩니다.

2. Kahn 알고리즘을 이용한 위상 정렬 구현 원리

위상 정렬을 구현하는 가장 보편적이고 효율적인 방식은 큐(Queue) 자료구조를 활용한 Kahn 알고리즘입니다. 이 방식은 너비 우선 탐색(BFS)과 유사한 구조를 가지며, 직관적인 로직 덕분에 다양한 시스템의 스케줄링 엔진에서 채택되고 있습니다.

2-1. 알고리즘의 단계별 동작 과정

그래프의 모든 노드에 대한 진입 차수를 계산하여 배열이나 테이블에 저장합니다.
초기 상태에서 진입 차수가 0인 모든 노드를 선택하여 큐(Queue)에 삽입합니다.
큐가 빌 때까지 다음의 과정을 반복 수행합니다.
- 큐에서 노드를 꺼내 결과 리스트에 추가합니다.
- 해당 노드에서 출발하는 모든 간선을 그래프에서 제거합니다. 즉, 연결된 인접 노드들의 진입 차수를 1씩 감소시킵니다.
- 이 과정에서 진입 차수가 새롭게 0이 된 노드들을 발견하면 즉시 큐에 삽입합니다.

2-2. 사이클 발생 여부의 판별 방법

만약 모든 노드를 방문하기 전에 큐가 비어버린다면, 해당 그래프에는 반드시 사이클(Cycle)이 존재한다고 판단할 수 있습니다. 위상 정렬 결과 리스트에 담긴 노드의 개수가 전체 노드의 개수보다 적다면 이는 유효한 위상 정렬이 아님을 의미하며, 시스템 설계 시 이러한 예외 처리는 필수적입니다.

3. 위상 정렬의 시간 복잡도 및 실무적 가치

위상 정렬 알고리즘은 모든 노드(V)와 간선(E)을 한 번씩 확인하는 과정을 거칩니다. 따라서 시간 복잡도는 O(V + E)로 계산되며, 이는 대규모 의존성 그래프에서도 매우 빠른 처리 속도를 보장합니다. 공간 복잡도 역시 노드와 간선의 정보를 저장하기 위한 수준인 O(V + E)를 유지합니다.

실무 적용 사례: 빌드 시스템과 워크플로우

현대적인 빌드 도구인 Gradle이나 Bazel은 수천 개의 모듈 간 의존성을 관리하기 위해 내부적으로 위상 정렬을 사용합니다. 또한, 데이터 파이프라인 엔진(Airflow 등)에서 작업 간의 실행 순서를 보장할 때도 이 알고리즘이 핵심적인 역할을 수행합니다. 기술 면접에서도 자료구조의 응용 능력을 평가하는 단골 주제로 등장하므로 완벽한 숙지가 필요합니다.


# 위상 정렬 알고리즘 Python 구현 예시
from collections import deque

def topological_sort(v, adj, indegree):
    result = [] # 알고리즘 결과를 담을 리스트
    q = deque() # 진입 차수가 0인 노드를 담을 큐

    # 1. 처음 시작 시 진입 차수가 0인 노드를 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    # 2. 큐가 빌 때까지 반복
    while q:
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입 차수에서 1 빼기
        for i in adj[now]:
            indegree[i] -= 1
            # 새롭게 진입 차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    # 모든 노드를 방문했다면 결과 반환, 아니면 사이클 발생
    return result if len(result) == v else "Cycle Detected"

[위상 정렬 핵심 요약]
1. 성립 조건: 사이클이 없는 방향 그래프(DAG) 환경에서만 유효한 정렬이 가능합니다.
2. 핵심 지표: 진입 차수(In-degree)가 0인 노드부터 순차적으로 처리하는 것이 로직의 핵심입니다.
3. 활용 분야: 소프트웨어 빌드 순서 결정, 작업 스케줄링, 데이터 파이프라인 의존성 관리 등에 필수적입니다.

코드 아카이브