위상 정렬 — 순서가 있는 작업을 올바르게 나열하기

과목 A를 들어야 과목 B를 들을 수 있고, B를 들어야 C를 들을 수 있습니다. 이런 선행 조건을 모두 만족하는 수강 순서는 어떻게 구할까요?

개념 정의

위상 정렬(Topological Sort)은 방향 비순환 그래프(DAG) 에서 모든 간선의 방향을 지키도록 노드를 일렬로 나열하는 것입니다.

간선 u → v가 있으면, 결과에서 u가 v보다 앞에 나와야 합니다.

왜 필요한가

순서가 있는 작업을 올바르게 배치해야 하는 상황은 매우 흔합니다.

대학 수강 순서 (선수 과목)
빌드 시스템의 task 실행 순서
스프레드시트 셀 계산 순서
Spring Bean 초기화 순서

방법 1: Kahn 알고리즘 (BFS 기반)

진입 차수(in-degree)가 0인 노드부터 큐에 넣고, 하나씩 처리하며 인접 노드의 진입 차수를 줄여갑니다.

JAVA

public static List<Integer> topologicalSortBFS(int n, List<List<Integer>> graph) {
    int[] inDegree = new int[n];

    // 진입 차수 계산
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) {
            inDegree[v]++;
        }
    }

    // 진입 차수 0인 노드를 큐에 삽입
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    List<Integer> result = new ArrayList<>();

    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);

        for (int next : graph.get(node)) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }

    // 사이클 탐지: 모든 노드가 결과에 포함되었는지 확인
    if (result.size() != n) {
        throw new IllegalStateException("그래프에 사이클이 존재합니다!");
    }

    return result;
}

동작 과정

PLAINTEXT

그래프: 0→1, 0→2, 1→3, 2→3

초기 진입 차수: [0, 1, 1, 2]
큐: [0]

Step 1: 0 처리 → 진입 차수: [-, 0, 0, 2], 큐: [1, 2]
Step 2: 1 처리 → 진입 차수: [-, -, 0, 1], 큐: [2]
Step 3: 2 처리 → 진입 차수: [-, -, -, 0], 큐: [3]
Step 4: 3 처리

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

방법 2: DFS 기반

DFS에서 노드의 종료 시간 역순 이 위상 정렬 결과입니다.

JAVA

public static List<Integer> topologicalSortDFS(int n, List<List<Integer>> graph) {
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfsTopo(graph, i, visited, stack);
        }
    }

    return new ArrayList<>(stack); // stack의 순서가 위상 정렬
}

private static void dfsTopo(List<List<Integer>> graph, int node,
                             boolean[] visited, Deque<Integer> stack) {
    visited[node] = true;

    for (int next : graph.get(node)) {
        if (!visited[next]) {
            dfsTopo(graph, next, visited, stack);
        }
    }

    stack.push(node); // 종료 시점에 스택에 삽입
}

DFS가 끝나는 순서(종료 시간)가 늦은 노드가 먼저 와야 하므로, 스택에 역순으로 쌓아서 꺼내면 됩니다.

두 방법의 비교

구분	Kahn (BFS)	DFS
자료구조	Queue + inDegree 배열	Stack + visited 배열
사이클 탐지	결과 크기로 판별	3-color(미방문/진행중/완료)로 판별
구현 난이도	직관적	재귀 기반
결과	진입 차수 0이 여러 개면 여러 결과 가능	동일

사이클 탐지

Kahn 알고리즘으로

JAVA

if (result.size() != n) {
    // 사이클이 존재 — 사이클 내 노드는 진입 차수가 0이 되지 못함
}

DFS로

JAVA

private static boolean dfsCycleCheck(List<List<Integer>> graph, int node,
                                      int[] state, Deque<Integer> stack) {
    state[node] = 1; // 진행중

    for (int next : graph.get(node)) {
        if (state[next] == 1) return true; // 사이클!
        if (state[next] == 0 && dfsCycleCheck(graph, next, state, stack)) {
            return true;
        }
    }

    state[node] = 2; // 완료
    stack.push(node);
    return false;
}

위상 정렬 + 최장 경로 (Critical Path)

DAG에서 위상 정렬 순서로 DP를 수행하면 최장 경로(임계 경로) 를 구할 수 있습니다.

JAVA

// 각 작업의 소요 시간이 주어질 때, 전체 완료까지의 최소 시간
public static int criticalPath(int n, List<List<int[]>> graph, int[] duration) {
    List<Integer> topoOrder = topologicalSortBFS(n, graph);
    int[] earliest = new int[n];

    // 각 노드의 가장 빠른 시작 시간
    for (int node : topoOrder) {
        for (int[] edge : graph.get(node)) {
            int next = edge[0];
            earliest[next] = Math.max(earliest[next],
                                       earliest[node] + duration[node]);
        }
    }

    int maxTime = 0;
    for (int i = 0; i < n; i++) {
        maxTime = Math.max(maxTime, earliest[i] + duration[i]);
    }
    return maxTime;
}

프로젝트 관리의 PERT/CPM 이 이 알고리즘의 응용입니다.

여러 가지 위상 정렬 결과

위상 정렬 결과는 유일하지 않을 수 있습니다. 모든 가능한 위상 정렬을 구하려면 백트래킹을 사용합니다.

JAVA

public static void allTopologicalSorts(int n, List<List<Integer>> graph,
                                        int[] inDegree, List<Integer> result,
                                        boolean[] visited) {
    if (result.size() == n) {
        System.out.println(result);
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i] && inDegree[i] == 0) {
            visited[i] = true;
            result.add(i);
            for (int next : graph.get(i)) inDegree[next]--;

            allTopologicalSorts(n, graph, inDegree, result, visited);

            // 되돌리기
            visited[i] = false;
            result.remove(result.size() - 1);
            for (int next : graph.get(i)) inDegree[next]++;
        }
    }
}

백엔드/실무에서의 연결

Gradle/Maven 빌드 순서

Gradle의 task 의존성은 DAG입니다. compileJava → processResources → jar → bootJar 같은 순서가 위상 정렬로 결정됩니다.

GROOVY

// Gradle task 의존성
task compile {
    dependsOn 'processResources'
}
task jar {
    dependsOn 'compile'
}

Spring Bean 초기화 순서

Spring 컨테이너는 Bean의 의존성 관계를 DAG로 구성하고, 위상 정렬 순서로 Bean을 생성합니다. @DependsOn 어노테이션은 이 DAG에 명시적인 간선을 추가합니다.

JAVA

@Configuration
public class AppConfig {
    @Bean
    @DependsOn("dataSource")  // dataSource가 먼저 초기화되어야 함
    public JdbcTemplate jdbcTemplate() {
        return new JdbcTemplate(dataSource());
    }
}

스프레드시트 셀 계산

Excel에서 A1 = B1 + C1이면, B1과 C1이 먼저 계산되어야 합니다. 셀 간의 참조 관계를 DAG로 만들고 위상 정렬하여 계산 순서를 결정합니다.

데이터 파이프라인

ETL(Extract, Transform, Load) 파이프라인에서 각 단계의 의존성을 위상 정렬로 관리합니다. Apache Airflow의 DAG가 대표적입니다.

PYTHON

# Airflow DAG 예시 (개념)
extract >> transform >> load
# extract가 완료되어야 transform 시작

주의할 점

사이클이 있는 그래프에서 위상 정렬을 시도하는 실수

위상 정렬은 DAG에서만 가능합니다. 사이클이 있으면 Kahn 알고리즘의 결과 노드 수가 전체 노드 수보다 적게 됩니다. 이를 사이클 탐지 조건으로 활용해야 합니다.

진입 차수가 0인 노드가 여러 개일 때 순서를 고정하지 않는 실수

위상 정렬의 결과는 유일하지 않을 수 있습니다. 사전순 등 특정 순서가 필요하면 일반 큐 대신 우선순위 큐를 사용해야 합니다.

정리

방법	핵심	사이클 탐지	시간 복잡도
Kahn (BFS)	진입 차수 0인 노드부터 처리	결과 크기 확인	O(V + E)
DFS	종료 시간 역순	3-color 상태 관리	O(V + E)

기억할 포인트:

위상 정렬은 DAG(사이클 없는 방향 그래프) 에서만 가능합니다.
Kahn 알고리즘은 진입 차수가 0인 노드를 큐에 넣어 BFS로 처리합니다.
위상 정렬 결과가 노드 수보다 적으면 사이클이 존재 합니다.
빌드 시스템, Spring Bean 초기화, 데이터 파이프라인 등 실무에서 폭넓게 사용됩니다.