위상 정렬: Topological Sort 토폴로지컬 정렬

Topological Sort (위상 정렬) 은 그래프 이론에서 매우 자주 등장하는 개념입니다.
한마디로 정리하면:

---

✅ Topological Sort란?

**방향성이 있는 그래프(DAG)**에서
모든 노드를 "선후 관계를 지키면서" 나열한 순서

즉,

• 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 경우
• 그 작업 순서를 찾는 게 바로 위상 정렬이에요.

✅ 조건: DAG 여야 함

Directed Acyclic Graph (DAG)란?

👉 '방향'이 있고, '사이클이 없는' 그래프

---

🔁 용어부터 찬찬히 살펴보면:

단어	의미
Directed	간선(선)에 방향이 있음 → A → B는 B → A와 다름
Acyclic	Cycle(순환) 이 없음 → 다시 자기 자신으로 돌아오는 경로가 없음
Graph	노드(점)들과 간선(선)으로 구성된 구조

---

📌 Topological Sort는 언제 사용하나?

🔧 대표적인 예시 상황들:

상황설명

상황	설명
작업 스케줄링	작업 간에 선후 관계가 있는 경우 (예: A 작업 끝나야 B 가능)
과목 선수 조건	선수과목 이수 순서 결정
빌드 순서	모듈끼리 의존성 있을 때 어떤 순서로 빌드할지
컴파일 순서	파일 간 의존성 해결

---

🔁 예시: 작업 순서 정하기

작업들: A, B, C, D  
조건: A → B, A → C, B → D, C → D

→ 이걸 그래프로 표현하면:

A → B → D  
 ↘   ↗
    C

→ 가능한 위상 정렬 결과:
`A → B → C → D` or `A → C → B → D` (여러 개 가능)

---

✅ Topological Sort 조건

• 그래프는 반드시 사이클이 없어야 함 → DAG (Directed Acyclic Graph)
• 사이클이 있다면 '위상 정렬' 불가능!

---

🔨 구현 방법 2가지

방법	설명	시간 복잡도
📥 Indegree + Queue (Kahn’s Algorithm)	진입차수 0인 노드를 큐에 넣고 처리	O(V + E)
📚 DFS 기반	후위 순회 Post-order 로 결과 뒤집기	O(V + E)

✅ Indegree(진입차수)란?

**한 노드로 "들어오는 간선의 개수"**를 말해요.

즉,
다른 노드들이 이 노드로 의존하거나,
이 노드 앞에서 먼저 처리해야 하는 작업 수라고 볼 수 있어요.

📌 예시 그래프

A → B → C

여기서 노드들의 indegree는?

노드	Indegree 값 (진입 차수)
A	0 (아무것도 안 들어옴)
B	1 (A → B)
C	1 (B → C)

---

✅ 왜 중요한가?

Topological Sort에서는 항상 Indegree == 0인 노드부터 처리해요.
왜냐하면, 이 노드는 다른 작업에 선행되지 않고 바로 실행 가능하다는 뜻이니까요.

---

🧠 그림으로 쉽게 이해하기

작업: A → B → C

처음:
- A: indegree 0 → 먼저 실행 가능

A 실행 후:
- B: indegree 1 → 0으로 줄어듦 → 실행 가능

B 실행 후:
- C: indegree 1 → 0으로 줄어듦 → 실행 가능

---

✅ 예시 코드 (Indegree 계산)

edges = [[0, 1], [1, 2]]
n = 3
indegree = [0] * n

for u, v in edges:
    indegree[v] += 1

print(indegree)  # 결과: [0, 1, 1]

---

✅ 용어 요약

용어	설명
Indegree	들어오는 간선 수 (선행 조건 몇 개인지)
Outdegree	나가는 간선 수 (이 노드가 선행 조건이 되는 노드 수)

---

✅ 파이썬 코드 예시 (Kahn’s Algorithm)

from collections import deque, defaultdict

def topological_sort(n, edges):
    # 방향 그래프를 인접 리스트 형태로 저장
    graph = defaultdict(list)
    
    # 각 노드의 진입차수 (indegree)를 저장할 리스트
    indegree = [0] * n

    # 그래프 구성 및 indegree 계산
    for u, v in edges:
        graph[u].append(v)     # u → v 라는 간선 추가
        indegree[v] += 1       # v의 진입차수 증가 (v로 들어오는 간선 하나 추가됨)

    # 진입차수가 0인 노드들을 먼저 큐에 넣음 (선행 조건이 없는 노드들)
    queue = deque([i for i in range(n) if indegree[i] == 0])

    # 결과 리스트: 위상 정렬 결과를 저장할 리스트
    result = []

    # 큐가 빌 때까지 반복
    while queue:
        node = queue.popleft()   # 진입차수 0인 노드 하나 꺼냄
        result.append(node)      # 처리된 노드를 결과에 추가

        # 현재 노드에서 나가는 간선에 연결된 이웃 노드들 확인
        for neighbor in graph[node]:
            indegree[neighbor] -= 1   # 현재 노드를 제거하므로 이웃의 진입차수 감소
            if indegree[neighbor] == 0:
                queue.append(neighbor)  # 진입차수가 0이 된 노드를 큐에 추가

    # 모든 노드를 결과에 담지 못했다면 → 사이클이 존재 (위상 정렬 불가능)
    return result if len(result) == n else []

 

✅ 위상 정렬 핵심 요약

단계	설명
1️⃣ indegree 계산	각 노드에 들어오는 간선 개수 저장
2️⃣ 큐 초기화	indegree == 0인 노드부터 시작
3️⃣ BFS 처리	하나씩 꺼내면서 연결된 노드의 indegree 감소
4️⃣ 정렬 결과 저장	선행 조건 없는 순서대로 저장
5️⃣ 사이클 여부 확인	전체 노드를 다 방문하지 못하면 사이클 존재함

---

🧠 추가 팁

• DAG(Directed Acyclic Graph)에서만 동작함!
• 위상 정렬의 결과는 여러 개가 될 수도 있음 (정답이 유일하지 않음)
• 사이클이 있으면 결과 리스트 길이가 n보다 작아짐 → return []

---

✅ 정리 요약

항목내용

핵심 개념	방향 그래프에서 선후 관계를 지키는 노드 순서 정렬
전제 조건	사이클이 없는 DAG여야 함
사용 예	작업/빌드 순서, 과목 이수, 의존성 문제 등
구현 방식	진입차수 기반(Kahn), DFS 기반(후위순회, Post-order)

---

✅ DFS 기반 위상 정렬이란?

DFS를 사용해서 그래프를 탐색한 다음,
모든 자식(하위 노드)을 다 방문한 후 현재 노드를 결과에 추가하는 방식입니다.

이걸 후위 순회 (post-order) 라고 해요.
탐색이 끝난 노드부터 스택에 쌓기 → 역순으로 정렬 결과 생성!

---

✅ 전제 조건

• 입력은 DAG (Directed Acyclic Graph) 여야 해요!
• 사이클이 있으면 위상 정렬은 불가능합니다 ❌

---

✅ 예제 코드 (DFS 후위순회 방식)

from collections import defaultdict

def dfs_topological_sort(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * n  # 0: 미방문, 1: 방문 중, 2: 방문 완료
    result = []
    has_cycle = [False]  # 사이클 체크용

    def dfs(node):
        if visited[node] == 1:
            has_cycle[0] = True  # 현재 방문 중인데 또 방문 → 사이클
            return
        if visited[node] == 2:
            return  # 이미 처리된 노드

        visited[node] = 1  # 방문 시작

        for neighbor in graph[node]:
            dfs(neighbor)

        visited[node] = 2  # 방문 완료
        result.append(node)  # 후위 순회: 자식 다 방문하고 나서 기록

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

    if has_cycle[0]:
        return []  # 사이클이 있으면 위상 정렬 불가

    return result[::-1]  # 스택에 넣은 순서 뒤집어서 반환

---

✅ 예시

n = 4
edges = [
    [0, 1],
    [1, 2],
    [2, 3]
]

print(dfs_topological_sort(n, edges))  # [0, 1, 2, 3]

---

🧠 핵심 정리

요소	설명
visited[node] == 1	방문 중인 노드 → 다시 방문하면 사이클 발생
result.append(node)	DFS 후위 순회로 결과 저장
[::-1]	결과 뒤집기 (가장 늦게 끝난 게 맨 앞에 와야 하니까)
사이클 있음?	DFS 중 방문 중인 노드를 다시 방문하면 발생

---

✅ Topological Sort: DFS vs Indegree 차이

방식	핵심 아이디어	특징
✅ DFS (후위 순회)	자식 먼저 다 방문 후 부모 기록	재귀적, 코드 간결
✅ Indegree (Kahn 알고리즘)	진입차수 0부터 차례로 제거	사이클 탐지 명확, BFS 기반