🔁 위상 정렬 (Topological Sort) 완전 정리

---

✅ 위상 정렬이란?

위상 정렬은 방향성이 있는 그래프(DAG)에서
모든 정점을 선후 관계를 지키며 일렬로 나열하는 알고리즘이다.

예를 들어, 어떤 작업이 다른 작업보다 먼저 수행되어야 한다면,
그 조건을 만족하는 작업 순서를 만들어낼 수 있다.

---

✅ 위상 정렬이 가능한 조건

• 방향 그래프여야 한다 (Directed)
• 사이클이 없어야 한다 (Acyclic)
  → 위상 정렬은 DAG (Directed Acyclic Graph)에서만 가능하다.

---

✅ 위상 정렬 예시

A → B → C
↓       ↑
D → E → F

위상 정렬 결과 예시: A D E F B C
※ 여러 정답이 존재할 수 있다 (조건만 만족하면 OK)

---

✅ BFS 방식 (진입차수 기반 위상 정렬)

✔️ 아이디어

• 각 노드의 진입차수(in-degree)를 센다
• 진입차수가 0인 노드를 큐에 넣는다
• 큐에서 꺼낸 후, 인접 노드들의 진입차수를 1씩 줄인다
• 진입차수가 0이 된 노드를 큐에 넣는다

✔️ 구현

from collections import deque

def topology_sort(n, graph):
    indegree = [0] * n
    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1

    queue = deque([i for i in range(n) 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)

    return result

# 예제 DAG
graph = {
    0: [2],
    1: [2, 3],
    2: [4],
    3: [4],
    4: []
}

print("위상 정렬 결과 (BFS):", topology_sort(5, graph))

---

✅ DFS 방식 (후위 순회 기반 위상 정렬)

✔️ 아이디어

• 아직 방문하지 않은 정점에 대해 DFS를 수행
• DFS가 종료되는 순서대로 결과 리스트에 담는다
• 결과를 역순(reverse) 하면 위상 정렬이 완성된다

✔️ 구현

def dfs_topo_sort(n, graph):
    visited = [False] * n
    result = []

    def dfs(v):
        visited[v] = True
        for neighbor in graph[v]:
            if not visited[neighbor]:
                dfs(neighbor)
        result.append(v)  # 종료 후 삽입

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

    result.reverse()
    return result

print("위상 정렬 결과 (DFS):", dfs_topo_sort(5, graph))

---

✅ BFS vs DFS 위상 정렬 비교

항목	BFS 방식 (진입차수)	DFS 방식 (후위 순회)
직관성	높음	낮음
사이클 감지	가능 (진입차수 남아있으면)	직접 구현 필요
순서 다양성	큐 처리 순서에 따라 달라짐	DFS 경로에 따라 달라짐
실전 활용	가장 많이 쓰임	트리 응용, 백트래킹에 어울림

---

✅ 시간 복잡도

• 인접 리스트 기준: O(V + E)
  (V: 정점 수, E: 간선 수)

---

✅ 위상 정렬이 쓰이는 곳

• 강의 수강 순서 (선수 과목 → 후속 과목)
• 작업 빌드 순서 (의존성 기반 작업 처리)
• 데이터 전처리 순서 자동 계산
• 컴파일, 배포, 명령어 실행 흐름 제어

---

🎯 마무리 요약

• 위상 정렬은 DAG(사이클 없는 방향 그래프)에서 가능한 정점 정렬 알고리즘이다.
• BFS 방식(진입차수)과 DFS 방식(후위 순회)이 있다.
• 순서가 고정되지 않아 정답이 여러 개일 수 있으며,
• 사이클이 존재하면 위상 정렬은 불가능하다.