대학교 수강신청 기간을 떠올려 보십시오. '자료구조' 과목을 수강하려면 반드시 'C언어 기초'를 먼저 이수해야만 하고, '운영체제'를 들으려면 '컴퓨터 구조'를 먼저 들어야 합니다. 이처럼 우리의 현실 세계와 프로젝트 관리(PM)에서는 "어떤 작업을 수행하기 전에 반드시 선행되어야만 하는 작업의 순서"가 명확하게 존재하는 경우가 무수히 많습니다. 소프트웨어 빌드 시스템(Make, Gradle)에서 소스 코드의 의존성을 파악하여 빌드 순서를 결정하는 과정 역시 마찬가지입니다. 이렇게 복잡하게 얽힌 선후 관계의 규칙을 절대 위배하지 않고, 모든 작업을 차례대로 나열하여 올바른 실행 순서를 찾아주는 마법의 알고리즘이 바로 '위상 정렬(Topological Sort)'입니다. 그래프 이론 중에서도 실생활 응용력이 가장 뛰어난 위상 정렬의 조건과 내부 동작 메커니즘을 상세히 해부해 드립니다.
1. 위상 정렬의 절대적인 전제 조건: DAG
위상 정렬은 방향 그래프(Directed Graph)의 모든 정점(Node)들을 방향성에 거스르지 않도록 일렬로 나열하는 알고리즘입니다. 하지만 세상의 모든 그래프에 위상 정렬을 적용할 수 있는 것은 아닙니다. 반드시 DAG(Directed Acyclic Graph, 사이클이 없는 방향 그래프) 형태여야만 한다는 절대적인 전제 조건이 붙습니다.
1-1. 왜 사이클(Cycle)이 있으면 안 될까?
만약 'A 과목'을 들으려면 'B 과목'을 선수강해야 하고, 'B 과목'을 들으려면 'C 과목'을 선수강해야 하는데, 'C 과목'을 들으려면 다시 'A 과목'을 선수강해야 한다고 상상해 보십시오. 이는 논리적인 모순(Deadlock)에 빠져 그 어떤 과목도 평생 수강을 시작할 수 없는 끔찍한 무한 루프 상태가 됩니다. 위상 정렬은 선후 관계를 정리하는 목적을 가지므로, 서로가 꼬리를 무는 순환(Cycle)이 존재한다면 정렬 자체가 수학적으로 불가능합니다. 따라서 위상 정렬 알고리즘은 정상적인 순서를 찾는 기능뿐만 아니라, 시스템에 모순된 사이클이 존재하는지 여부를 판별해 내는 검증 도구로도 훌륭하게 쓰입니다.
2. 위상 정렬의 핵심 원리: 진입 차수 (In-degree)
위상 정렬을 코드로 깔끔하게 구현하기 위해서는 '진입 차수(In-degree)'라는 개념을 완벽히 이해해야 합니다. 진입 차수란, "나에게로 들어오는(나를 향하는) 화살표의 개수"를 의미합니다. 대학교 수강신청에 비유하자면, 진입 차수는 "내가 이 과목을 듣기 위해 먼저 들어야 하는 선수 과목의 개수"입니다. 당연히 당장 수강 신청이 가능한 과목은 진입 차수가 0인 과목(선수 과목이 필요 없는 기초 과목)뿐입니다.
2-1. 큐(Queue)를 활용한 4단계 동작 알고리즘 (Kahn's Algorithm)
가장 대중적이고 이해하기 쉬운 큐 기반의 탐색 과정을 시뮬레이션해 봅니다.
- 초기화 및 차수 계산: 그래프의 모든 노드에 대해, 자신을 향해 들어오는 간선의 개수(진입 차수)를 세어서 배열에 저장합니다.
- 시작점 찾기: 계산된 배열을 훑어보고, 진입 차수가 0인(즉, 당장 실행 가능한) 모든 노드들을 큐(Queue)에 한꺼번에 삽입합니다.
- 작업 실행 및 연결 해제: 큐에서 노드를 하나 꺼냅니다(Dequeue). 이 노드는 이제 작업이 완료된 것입니다. 따라서 이 노드에서 출발하여 다른 노드로 뻗어 나가는 모든 화살표(간선)를 가위로 잘라 제거합니다. 이로 인해 이 노드에 의존하고 있던 다음 노드들의 진입 차수는 각각 1씩 감소하게 됩니다.
- 새로운 시작점 삽입: 화살표를 제거하는 과정에서, 새롭게 진입 차수가 0이 된 노드(선행 조건이 모두 충족된 노드)가 생겼다면, 주저 없이 그 노드를 큐에 새롭게 삽입합니다.
큐가 텅 빌 때까지 3번과 4번의 과정을 무한 반복합니다. 이때 큐에서 꺼내어진 노드들의 순서가 바로 완벽한 위상 정렬의 결과물이 됩니다.
3. 결과 분석 및 한계점
만약 그래프에 총 $V$개의 정점이 있는데, 큐에서 꺼낸 정점의 개수가 $V$개에 미치지 못하고 큐가 텅 비어 알고리즘이 도중에 종료되어 버렸다면 무슨 뜻일까요? 이는 그래프 어딘가에 서로 화살표를 주고받는 사이클(Cycle)이 숨어있어, 진입 차수가 0이 되는 노드가 영원히 나오지 않는 꽉 막힌 상태(Deadlock)에 빠졌음을 강력하게 의미합니다. 또한, 한 단계에서 큐에 진입 차수가 0인 노드가 2개 이상 동시에 들어간다면, 이 둘은 순서가 바뀌어도 무방하므로 위상 정렬의 정답은 한 가지가 아니라 여러 개가 될 수 있음을 시사합니다. 시간 복잡도는 모든 정점($V$)과 간선($E$)을 정확히 한 번씩만 훑고 지나가므로, 매우 효율적인 $O(V + E)$를 자랑합니다.
1. 위상 정렬(Topological Sort)은 일의 선후 관계가 복잡하게 얽힌 방향 그래프에서, 규칙을 위배하지 않고 모든 작업을 순서대로 나열하는 알고리즘입니다.
2. 반드시 사이클(순환)이 없는 방향 그래프, 즉 DAG(Directed Acyclic Graph) 환경에서만 작동하며 사이클 존재 여부를 검증하는 데에도 쓰입니다.
3. 나를 향하는 화살표의 개수인 진입 차수(In-degree)가 0인 노드들을 큐에 차례대로 담고 간선을 끊어나가는 방식으로 $O(V+E)$의 빠른 속도로 정답을 도출합니다.