[C++ - TIL] 위상 정렬(Topological Sort)의 메커니즘과 STL 컨테이너의 활용

🎮 주제 : 위상 정렬(Topological Sort)의 메커니즘과 STL 컨테이너의 활용

태그 : #C++ #알고리즘 #위상정렬 #DAG #진입차수 #STL #자료구조

---

📌 학습 요약

• 위상 정렬(Topological Sort) : 작업의 선후 관계가 있는 방향 그래프에서 순서를 어기지 않고 나열하는 알고리즘으로, 반드시 **사이클이 없는 방향 그래프(DAG)**에서만 성립함을 이해
• 진입 차수(In-degree)의 활용 : "나를 가리키는 화살표가 0개"라는 의미가 곧 "사전 작업이 완료되어 지금 바로 시작 가능함"을 의미한다는 핵심 논리 파악
• 큐(Queue) 기반 프로세스 : 진입 차수가 0인 노드를 큐에 넣고, 해당 노드와 연결된 간선을 제거하며 연쇄적으로 다음 작업 가능 후보를 찾는 과정 습득
• 효율적인 자료구조 선택 : 정점 관리를 위한 unordered_set, 인접 리스트와 차수 기록을 위한 unordered_map 등 각 컨테이너의 시간 복잡도**(O(1))**와 사용 목적 정립
• 헤더 포함(Include)의 원칙 : 내부 구현에 의해 우연히 작동하는 코드가 아닌, 표준을 준수하기 위해 사용하는 모든 STL 헤더를 명시적으로 선언해야 함을 숙지

---

🛠 주요 코드 및 구현 상세

1. 간선 삽입 및 진입 차수 계산

void insert(const T & i, const T & j) {
    adjacencyList[i].push_back(j); // i -> j 방향 간선 추가
    degree[j]++;                   // 들어오는 노드(j)의 진입 차수 증가

    vertices.insert(i);            // 전체 정점 집합에 추가
    vertices.insert(j);

    // 출발 노드(i)의 차수가 등록되지 않았다면 0으로 초기화
    if (degree.count(i) == false) {
        degree[i] = 0;
    }
}

2. 큐를 이용한 위상 정렬 실행 (Kahn's Algorithm)

void search() {
    queue<T> q;
    vector<T> result;

    // 1. 초기 진입 차수가 0인(바로 시작 가능한) 노드들을 큐에 삽입
    for (auto v : vertices) {
        if (degree[v] == 0) {
            q.push(v);
        }
    }

    // 2. 큐가 빌 때까지 반복하며 정렬 진행
    while (!q.empty()) {
        T x = q.front(); 
        q.pop();
        result.push_back(x);

        // 현재 노드(x)와 연결된 다음 노드(next)들의 차수 감소
        for (T next : adjacencyList[x]) {
            degree[next]--;
            // 차수가 0이 되면 이제 시작 가능하므로 큐에 삽입
            if (degree[next] == 0) {
                q.push(next);
            }
        }
    }

    // 3. 결과 출력
    for (T v : result) cout << v << " ";
    cout << endl;
}

---

✅ 주요 문법 및 개념 정리

컨테이너 / 개념 특징 활용 목적

unordered_map	해시 기반 Key-Value 저장	인접 리스트 및 노드별 진입 차수 관리
unordered_set	중복 없는 원소 저장	전체 정점(Vertices) 목록 유지
In-degree 0	선행 조건이 없는 상태	위상 정렬의 시작점(Entry Point)
#include <vector>	동적 배열 헤더	인접 리스트 저장 시 필수 (명시적 선언 권장)

💡 알고리즘 인사이트 : 왜 사이클이 있으면 안 될까?

• 사이클(A → B → A)이 존재하면, 서로가 서로의 선행 조건이 되어 두 노드 모두 진입 차수가 결코 0이 되지 않음
• 결과적으로 큐에 들어가지 못하게 되어 위상 정렬이 불완전하게 종료됨

---

✨ 느낀 점

• "진입 차수 0"이 작업의 시작 지점을 의미한다는 수학적 개념을 코드로 구현해 보며 알고리즘의 직관적인 흐름을 이해함
• STL 컨테이너들이 서로를 내부적으로 참조하더라도, 이식성 높은 코드를 위해 헤더를 직접 포함해야 한다는 실무적인 규칙을 배움
• 복잡한 의존성 관계(예: 게임 스킬 트리, 빌드 시스템)를 위상 정렬이라는 하나의 논리로 해결할 수 있다는 점이 매우 흥미로웠음
• 코드가 복잡해질수록 각 컨테이너(map, set, vector)의 역할 분담을 명확히 하는 설계 능력이 중요함을 느낌