위상 정렬 (Topological Sort)

“누가 먼저?”를 정리하는 기술: 위상 정렬 (Topological Sort)

게임 퀘스트를 하다 보면 이런 말을 종종 본 적 있을 것이다. “퀘스트 A를 완료한 뒤에만 퀘스트 B를 할 수 있습니다.” 혹은 학교에서는 “수학II는 수학I을 들은 다음에 수강할 수 있습니다.” 이처럼 어떤 작업이 선행되어야 하는 관계가 있을 때, 우리는 전체 순서를 어떻게 정할 수 있을까?

1. 위상 정렬이란?

위상 정렬(topological sort)은 순환이 없는 유향 그래프(DAG)에서 모든 노드를 선행 조건을 지키면서 순서대로 나열하는 알고리즘이다.

예제: 과목 이수 순서

• 수학I → 수학II
• 물리학 → 전자회로
• 수학II → 전자회로

이 경우 전체 이수 순서는 수학I → 수학II → 물리학 → 전자회로 또는 물리학 → 수학I → 수학II → 전자회로 처럼 여러 가지가 될 수 있다. 그러나 어떤 경우든 수학I이 수학II보다 먼저, 수학II가 전자회로보다 먼저임은 지켜야 한다.

2. 위상 정렬이 필요한 이유

위상 정렬은 다음과 같은 상황에서 반드시 필요하다:

• 과목 수강 순서
• 패키지 설치 순서 (예: A가 설치되기 전에 B는 설치될 수 없음)
• 작업의 선후 관계가 주어진 공정 관리
• 게임 퀘스트의 진행 조건

즉, 순서를 정하기 전에 무엇이 먼저인가?를 따지는 모든 상황에서 위상 정렬은 강력한 도구가 된다.

3. 알고리즘: 카안(Kahn)의 위상 정렬

1. 모든 노드의 진입 차수(in-degree)를 구한다.
2. 진입 차수가 0인 노드를 큐에 넣는다.
3. 큐에서 꺼낸 노드를 결과에 추가하고, 그 노드에서 나가는 간선을 제거한다.
4. 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
5. 모든 노드를 처리하면 종료된다.

4. 예제로 이해하기: 백준 2252번 줄 세우기

학생들의 키 순서를 전부 모르는 상황에서, 일부 학생들의 “누가 누구보다 큰가” 정보만을 이용해 전체 순서를 유추해야 한다.

예시 입력

3 2
1 3
2 3

• 1번 학생은 3번 학생보다 앞에 서야 함
• 2번 학생도 3번 학생보다 앞에 서야 함

따라서 가능한 줄 서는 순서는 1 2 3 또는 2 1 3이다. 조건만 지키면 여러 순서가 가능하다는 것이 위상 정렬의 특징이다.

파이썬 구현

from collections import deque

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
indeg = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    indeg[b] += 1

q = deque(i for i in range(1, N + 1) if indeg[i] == 0)
res = []

while q:
    cur = q.popleft()
    res.append(cur)
    for nxt in adj[cur]:
        indeg[nxt] -= 1
        if indeg[nxt] == 0:
            q.append(nxt)

print(*res)

5. 정리

위상 정렬은 선후 조건이 있는 여러 개의 작업을 순서대로 처리할 때 사용하는 기본적인 알고리즘이다. 그 핵심은 진입 차수가 0인 작업을 차례대로 선택하며 전체 순서를 정리해 나가는 데 있다.

위상 정렬 문제 추천

• 2252번: 줄 세우기 (기본)
• 1005번: ACM Craft (작업 시간 포함)
• 1516번: 게임 개발 (복합 조건)

 

위상 정렬을 설명하는 블로그 추천

---

🔹 1. LimeCoding: 위상 정렬이란?

게임의 기술 트리와 문명5의 예시를 통해 위상 정렬의 개념을 설명합니다. 진입 차수 기반의 알고리즘 구현 과정을 시각적으로 보여주어 이해를 돕습니다.​LimeCodingVelog+5Hello, World & Me+5한재훈 개발 블로그+5

 

🔹 2. 디아블로2 인벤: 위상 정렬을 쉽게 설명해볼게요

라면 끓이기, 택배 포장, 수업 순서 등 일상적인 비유를 통해 위상 정렬을 설명합니다. 복잡한 용어 없이 누구나 이해할 수 있도록 구성되어 있습니다.​인벤 - No.1 게임 미디어 플랫폼

🔹 3. Hello, World & Me: 위상 정렬 완벽 정리

위상 정렬의 정의부터 알고리즘 흐름, 파이썬 코드 예제까지 체계적으로 정리되어 있습니다. 백준 문제와의 연계로 실전 적용에도 도움이 됩니다.​Hello, World & Me+1네이버 블로그+1

🔹 4. 네이버 블로그: DFS 응용 Part.1 - 위상 정렬

DFS를 활용한 위상 정렬 구현 방법을 설명하며, 메이플스토리의 스킬 트리를 예시로 들어 개념을 쉽게 전달합니다.​네이버 블로그+1개발하는 지토+1

🔹 5. 4Legs Archives: 위상 정렬

방탈출 게임을 비유로 사용하여 위상 정렬의 개념을 설명합니다. 진입 차수와 진출 차수의 개념을 시각적으로 이해할 수 있도록 구성되어 있습니다.​Velog+74Legs_Archives+7한재훈 개발 블로그+7

위상 정렬을 설명하는 영상 추천

🎓 1. 동빈나: 실전 알고리즘 강좌 - 27강 위상 정렬

• 설명: 큐(Queue)를 활용한 위상 정렬 알고리즘을 자세히 설명하며, 실전 문제 풀이에 초점을 맞춘 강의입니다.
• 특징: 백준 문제와 연계되어 실전 감각을 키우기에 적합합니다.https://m.blog.naver.com/ndb796/221236874984
  ​

25. 위상 정렬(Topology Sort)

 

---

🧠 2. 코딩인터뷰: 위상 정렬 (Topological Sort)

• 설명: 위상 정렬의 개념과 다양한 활용 사례를 소개하며, 이론과 실무를 연결해주는 강의입니다.
• 특징: 빌드 시스템, 딥러닝 그래프 등 실제 응용 분야에 대한 설명이 포함되어 있습니다.
  
  

  [이것이 코딩 테스트다 with Python] 36강 위상 정렬

  https://youtu.be/xeSz3pROPS8​

 

bfs 기반 코드

아래는 Kahn's Algorithm(BFS 기반 위상 정렬)을 사용한 직관적이고 이해하기 쉬운 Python 코드이다.

from collections import deque, defaultdict

# 그래프 정의 (간선 리스트로 주어짐)
edges = [
    (1, 2),
    (1, 3),
    (3, 4),
    (5, 6),
    (6, 4)
]
n = 6  # 노드 개수

# 진입 차수 리스트와 인접 리스트 초기화
indegree = [0] * (n + 1)
graph = defaultdict(list)

# 그래프 구성
for a, b in edges:
    graph[a].append(b)
    indegree[b] += 1

# 진입 차수가 0인 노드를 큐에 삽입
queue = deque()
for i in range(1, n + 1):
    if indegree[i] == 0:
        queue.append(i)

# 위상 정렬 결과 리스트
result = []

while queue:
    node = queue.popleft()
    result.append(node)
    
    for neighbor in graph[node]:
        indegree[neighbor] -= 1
        if indegree[neighbor] == 0:
            queue.append(neighbor)

# 출력
if len(result) == n:
    print("위상 정렬 결과:", result)
else:
    print("사이클이 있어 위상 정렬이 불가능함.")

dfs기반 코드

DFS(깊이 우선 탐색) 기반 위상 정렬은 후위 순회(post-order) 원리를 활용한다.
즉, 자식 노드를 모두 방문한 뒤 부모 노드를 기록하면 위상 정렬이 성립된다.

다음은 DFS 기반 위상 정렬을 구현한 쉬운 코드이다:

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

# 그래프 정의 (간선 리스트로 주어짐)
edges = [
    (1, 2),
    (1, 3),
    (3, 4),
    (5, 6),
    (6, 4)
]
n = 6  # 노드 개수

# 인접 리스트 생성
graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)

visited = [False] * (n + 1)
result = []
on_stack = [False] * (n + 1)  # 사이클 검출용

def dfs(node):
    visited[node] = True
    on_stack[node] = True

    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor)
        elif on_stack[neighbor]:
            print("사이클이 존재함 → 위상 정렬 불가")
            exit()

    on_stack[node] = False
    result.append(node)

# 모든 노드에 대해 DFS 수행 (연결되지 않은 노드 고려)
for i in range(1, n + 1):
    if not visited[i]:
        dfs(i)

# 결과를 뒤집어서 위상 정렬 순서 완성
result.reverse()
print("위상 정렬 결과:", result)