[알고리즘] 위상정렬

코딩 테스트가 끝나고 사람들 후기를 보는데 위상 정렬로 풀면 금방 풀리는 문제였다고 하는데 위상정렬이란 뭘까?

위상정렬(Topological Sorting) 개념

정의:

위상정렬은 방향 그래프(DAG, Directed Acyclic Graph)에서 사용되는 정렬 방법으로,

모든 간선 (u → v)에 대해 u가 v보다 먼저 나오도록 정렬하는 것을 말한다.

즉, 선행 관계가 있는 작업들을 순서대로 나열할 때 사용한다. (A작업을 한 뒤 B를 수행할 수 있다와 같은 유형)

조건:

• 반드시 사이클 없는 방향 그래프(DAG)이어야 한다.
• 사이클이 있으면 위상정렬이 불가능하다.

예시:

A → B → C
A → D

가능한 위상정렬: A, B, D, C 또는 A, D, B, C

- 관련 문제

https://www.acmicpc.net/problem/2252

https://www.acmicpc.net/problem/2623

구현 방법

(1) DFS 기반

1. 방문하지 않은 노드에서 DFS 수행
2. DFS 탐색이 끝난 노드를 스택에 넣음
3. 스택을 뒤집으면 위상정렬 순서

장점: 구현 간단

단점: 사이클 검사 추가 필요

(2) Kahn 알고리즘(BFS 기반)

1. 모든 노드의 진입 차수(in-degree) 계산
2. 진입 차수가 0인 노드를 큐에 넣음
3. 큐에서 노드를 하나씩 빼면서 결과에 추가, 연결된 노드의 진입 차수 1 감소
4. 진입 차수가 0이 된 노드를 큐에 넣음
5. 모든 노드 처리 후 결과 출력

장점: 사이클이 있는지 쉽게 체크 가능

---

✅ 파이썬 구현 예제

(A) DFS 기반

def topological_sort_dfs(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]  # 뒤집어서 반환

# 예제 그래프
graph = {
    'A': ['B', 'D'],
    'B': ['C'],
    'C': [],
    'D': ['C']
}

print(topological_sort_dfs(graph))

---

(B) Kahn 알고리즘(BFS 기반) ⭐

#장점: 사이클 검출 가능
from collections import deque

def topological_sort_kahn(graph):
    in_degree = {u: 0 for u in graph}  # 진입차수 초기화
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque([u for u in graph if in_degree[u] == 0])
    result = []

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

    if len(result) != len(graph):
        return "Cycle detected!"
    return result

# 예제 그래프
graph = {
    'A': ['B', 'D'],
    'B': ['C'],
    'C': [],
    'D': ['C']
}

print(topological_sort_kahn(graph))
#['A', 'B', 'D', 'C']

✅ DFS와 BFS 모두 결과는 가능한 위상정렬 중 하나를 반환한다.

문제 풀어보기!

백준 2623번: 음악프로그램 Gold3

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split()) #가수, 보조 PD
singers = {i:[] for i in range(1, n+1)}
in_degree = {i:0 for i in range(1, n+1)}
for _ in range(m):
    seq = list(map(int, input().split()))
    for i in range(1, seq[0]):
        singers[seq[i]].append(seq[i+1])
        in_degree[seq[i+1]] += 1
q = deque([u for u in in_degree if in_degree[u]==0])
rst = []
while q:
    now = q.popleft()
    rst.append(now)
    for nxt in singers[now]:
        in_degree[nxt] -= 1
        if in_degree[nxt] == 0:
            q.append(nxt)
if len(rst) != n: print(0) #불가능한 경우는 cycle
else:
    for r in rst:
        print(r)