위상 정렬 (Topological Sort)

개념

방향 그래프에서 선행 순서를 지키며 모든 정점을 나열하는 알고리즘

**사이클이 없는 방향 그래프(DAG)**에서만 가능

---

시간복잡도

구현 방식	시간복잡도
DFS 기반	O(V + E)
진입 차수 (BFS) 기반	O(V + E)
공간복잡도	O(V + E)

---

특징

장점

• 순서 보장: 선행 관계 유지
• 빠른 속도: O(V + E)
• 사이클 탐지: 위상 정렬 불가 = 사이클 존재

단점

• DAG만 가능: 사이클 있으면 불가
• 유일하지 않음: 여러 결과 가능

DAG (Directed Acyclic Graph)

• 방향 그래프: 간선에 방향 있음
• 비순환: 사이클이 없음
• 예시: 과목 선수과목, 작업 순서

---

구현 방법

진입 차수 기반 (Kahn’s Algorithm)

from collections import deque
 
def topological_sort_kahn(n, edges):
    """위상 정렬 - 진입 차수 기반"""
    # 그래프 및 진입 차수 초기화
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
 
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
 
    # 진입 차수가 0인 정점을 큐에 추가
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)
 
    result = []
 
    while queue:
        current = queue.popleft()
        result.append(current)
 
        # 인접 정점의 진입 차수 감소
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
 
            # 진입 차수가 0이 되면 큐에 추가
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    # 사이클 확인
    if len(result) != n:
        return None  # 사이클 존재
 
    return result
 
# 테스트
edges = [
    (0, 1), (0, 2),
    (1, 3), (2, 3)
]
 
print(topological_sort_kahn(4, edges))  # [0, 1, 2, 3] 또는 [0, 2, 1, 3]
 
# 시간복잡도: O(V + E)
# 공간복잡도: O(V + E)

---

DFS 기반

def topological_sort_dfs(n, edges):
    """위상 정렬 - DFS 기반"""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
 
    visited = [False] * n
    stack = []
 
    def dfs(v):
        visited[v] = True
 
        for neighbor in graph[v]:
            if not visited[neighbor]:
                dfs(neighbor)
 
        # 후위 순회 순서로 스택에 추가
        stack.append(v)
 
    # 모든 정점에서 DFS
    for i in range(n):
        if not visited[i]:
            dfs(i)
 
    # 스택을 역순으로 반환
    return stack[::-1]
 
# 테스트
edges = [
    (0, 1), (0, 2),
    (1, 3), (2, 3)
]
 
print(topological_sort_dfs(4, edges))  # [0, 2, 1, 3] 또는 [0, 1, 2, 3]
 
# 시간복잡도: O(V + E)

---

사이클 탐지 포함

def topological_sort_with_cycle_detection(n, edges):
    """사이클 탐지 포함"""
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
 
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
 
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)
 
    result = []
    count = 0
 
    while queue:
        current = queue.popleft()
        result.append(current)
        count += 1
 
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    # 처리된 정점 수가 n보다 적으면 사이클
    if count != n:
        return None, "사이클 존재"
 
    return result, "성공"
 
# 테스트
# 사이클 있는 경우
edges_with_cycle = [
    (0, 1), (1, 2), (2, 0)
]
 
result, msg = topological_sort_with_cycle_detection(3, edges_with_cycle)
print(msg)  # "사이클 존재"

---

동작 과정

그래프: (선수과목 관계)
    0 → 1
    ↓   ↓
    2 → 3

간선: (0→1), (0→2), (1→3), (2→3)

진입 차수:
  0: 0 (선수과목 없음)
  1: 1 (0 필요)
  2: 1 (0 필요)
  3: 2 (1, 2 필요)

1단계: 진입 차수 0인 정점
  큐: [0]
  결과: []

2단계: 0 처리
  0의 인접: 1, 2
  진입 차수: 1→0, 2→0
  큐: [1, 2]
  결과: [0]

3단계: 1 처리
  1의 인접: 3
  진입 차수: 3→1
  큐: [2]
  결과: [0, 1]

4단계: 2 처리
  2의 인접: 3
  진입 차수: 3→0
  큐: [3]
  결과: [0, 1, 2]

5단계: 3 처리
  큐: []
  결과: [0, 1, 2, 3]

완료: [0, 1, 2, 3]

---

템플릿

from collections import deque
 
def topological_sort_template(n, edges):
    # 1. 그래프 및 진입 차수 초기화
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
 
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
 
    # 2. 진입 차수 0인 정점 큐에 추가
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)
 
    # 3. 위상 정렬
    result = []
 
    while queue:
        current = queue.popleft()
        result.append(current)
 
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    # 4. 사이클 확인
    if len(result) != n:
        return None
 
    return result

---

핵심 요약

개념	설명
원리	선행 순서를 지키며 정점 나열
시간복잡도	O(V + E)
공간복잡도	O(V + E)
적용 조건	DAG (사이클 없는 방향 그래프)
활용	작업 순서, 선수과목

---

구현 방식 비교

방식	장점	단점
진입 차수 (Kahn)	사이클 탐지 쉬움	추가 배열 필요
DFS	간단한 구현	사이클 탐지 복잡

---

주의사항

1. DAG 확인

# 사이클이 있으면 위상 정렬 불가
def is_dag(n, edges):
    result = topological_sort_kahn(n, edges)
    return result is not None

2. 여러 정답

# 위상 정렬 결과는 유일하지 않음
# [0, 1, 2, 3]도 가능
# [0, 2, 1, 3]도 가능

3. 간선 방향

# 반드시 방향 그래프
# u → v: u가 v보다 먼저
edges = [(0, 1)]  # 0 → 1 (0이 1보다 먼저)

---

자주 나오는 문제 유형

1. 기본 위상 정렬

문제: 선수과목 순서대로 수강

def course_schedule(n, prerequisites):
    """과목 수강 순서"""
    result = topological_sort_kahn(n, prerequisites)
 
    if result is None:
        return "불가능"  # 사이클 존재
 
    return result
 
# 테스트
# (A, B): B를 듣기 전에 A를 들어야 함
prerequisites = [
    (0, 1), (0, 2),
    (1, 3), (2, 3)
]
 
print(course_schedule(4, prerequisites))  # [0, 1, 2, 3]

---

2. 사이클 탐지

문제: 순환 참조가 있는지 확인

def can_finish(n, prerequisites):
    """모든 과목을 들을 수 있는지"""
    result = topological_sort_kahn(n, prerequisites)
 
    return result is not None
 
# 테스트
# 사이클 있는 경우
prerequisites = [(0, 1), (1, 0)]
print(can_finish(2, prerequisites))  # False
 
# 사이클 없는 경우
prerequisites = [(0, 1), (1, 2)]
print(can_finish(3, prerequisites))  # True

---

3. 위상 정렬 순서 출력

문제: 백준 2252번 - 줄 세우기

def line_up(n, comparisons):
    """키 순서대로 줄 세우기"""
    result = topological_sort_kahn(n, comparisons)
 
    if result is None:
        return []
 
    return result
 
# 테스트
# (A, B): A가 B보다 앞에
comparisons = [
    (1, 3), (2, 3)
]
 
print(line_up(3, comparisons))  # [0, 1, 2] 또는 [0, 2, 1]

---

4. 작업 순서

문제: 선행 작업을 완료해야 하는 작업 순서

def task_order(n, dependencies):
    """작업 순서"""
    result = topological_sort_kahn(n, dependencies)
 
    if result is None:
        return "순환 의존성"
 
    return result
 
# 테스트
# (A, B): A 완료 후 B 가능
dependencies = [
    (0, 2), (1, 2),
    (2, 3), (2, 4)
]
 
print(task_order(5, dependencies))  # [0, 1, 2, 3, 4]

---

5. 빌드 순서

문제: 프로그래머스 - 빌드 순서

def build_order(n, dependencies):
    """빌드 순서 (LeetCode 210)"""
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
 
    for prereq, course in dependencies:
        graph[prereq].append(course)
        in_degree[course] += 1
 
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)
 
    result = []
 
    while queue:
        current = queue.popleft()
        result.append(current)
 
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    return result if len(result) == n else []
 
# 테스트
dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]]
print(build_order(4, dependencies))  # [0, 1, 2, 3] 또는 [0, 2, 1, 3]

---

6. 모든 위상 정렬 결과

문제: 가능한 모든 위상 정렬 순서

def all_topological_sorts(n, edges):
    """모든 위상 정렬 결과"""
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
 
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
 
    result = []
    current = []
 
    def backtrack(in_deg):
        # 진입 차수 0인 정점들
        available = [i for i in range(n) if in_deg[i] == 0]
 
        if not available:
            if len(current) == n:
                result.append(current[:])
            return
 
        for v in available:
            current.append(v)
            new_in_deg = in_deg[:]
            new_in_deg[v] = -1  # 방문 표시
 
            for neighbor in graph[v]:
                new_in_deg[neighbor] -= 1
 
            backtrack(new_in_deg)
            current.pop()
 
    backtrack(in_degree)
    return result
 
# 테스트
edges = [(0, 1), (0, 2)]
print(all_topological_sorts(3, edges))
# [[0, 1, 2], [0, 2, 1]]

---

7. 최소 학기 수

문제: 선수과목을 고려한 최소 학기

def minimum_semesters(n, prerequisites):
    """최소 학기 수"""
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
 
    for u, v in prerequisites:
        graph[u].append(v)
        in_degree[v] += 1
 
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append((i, 1))  # (정점, 학기)
 
    max_semester = 0
    count = 0
 
    while queue:
        current, semester = queue.popleft()
        max_semester = max(max_semester, semester)
        count += 1
 
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append((neighbor, semester + 1))
 
    return max_semester if count == n else -1
 
# 테스트
prerequisites = [
    (0, 1), (0, 2),
    (1, 3), (2, 3)
]
 
print(minimum_semesters(4, prerequisites))  # 3

---

추천 연습 문제

기초

• 백준 2252번 - 줄 세우기
• 백준 1766번 - 문제집

중급

• 백준 2623번 - 음악프로그램
• 백준 1005번 - ACM Craft
• LeetCode 207 - Course Schedule
• LeetCode 210 - Course Schedule II

고급

• 백준 3665번 - 최종 순위
• LeetCode 1203 - Sort Items by Groups

---

위상 정렬 변형

1. 우선순위 포함

import heapq
 
def topological_sort_priority(n, edges):
    """사전순 위상 정렬"""
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
 
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
 
    # 우선순위 큐 사용
    heap = []
    for i in range(n):
        if in_degree[i] == 0:
            heapq.heappush(heap, i)
 
    result = []
 
    while heap:
        current = heapq.heappop(heap)
        result.append(current)
 
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                heapq.heappush(heap, neighbor)
 
    return result if len(result) == n else None
 
# 사전순으로 가장 앞선 위상 정렬

---

2. 그룹별 위상 정렬

def topological_sort_groups(n, edges, groups):
    """그룹 내부 + 그룹 간 위상 정렬"""
    # 복잡한 구현 - 생략
    pass

---

언제 사용할까?

사용 가능

• 선행 관계: 순서가 정해진 작업
• DAG: 사이클 없는 방향 그래프
• 컴파일 순서: 의존성 관리
• 빌드 시스템: Makefile 등

사용 불가

• 사이클 있음: 순환 의존성
• 무방향 그래프: 방향 필요
• 순서 무관: 위상 정렬 불필요

결론: 선행 관계가 있는 작업 순서 결정에 최적!