[WEEK03] 위상 정렬

🔍 위상 정렬이란?

위상 정렬(Topological Sort)은 방향 그래프(DAG, Directed Acyclic Graph)에서 선후 관계를 유지하면서 모든 정점을 나열하는 정렬 기법이다. 즉, 어떤 작업이 다른 작업보다 먼저 수행되어야 할 때, 그 순서를 결정하는 알고리즘이다.

📌 위상 정렬의 특징

1. 사이클이 없는 방향 그래프(DAG)에서만 적용 가능
2. 여러 가지 정렬 결과가 나올 수 있음 (순서를 지키는 여러 가지 방법이 존재할 수 있음)
3. 진입 차수(indegree) 개념을 활용하여 구현 가능

⚙️ 위상 정렬 알고리즘 (Kahn’s Algorithm)

위상 정렬은 주로 진입 차수(indegree) 기반의 큐(BFS) 방식과 DFS 기반의 스택 방식으로 구현할 수 있다. 가장 많이 사용되는 방법은 BFS 방식인 Kahn’s Algorithm이다.

✅ 알고리즘 과정 (BFS 방식)

1. 진입 차수(indegree)를 저장하는 배열을 만든다.
2. 진입 차수가 0인 노드를 큐에 삽입한다.
3. 큐에서 노드를 하나씩 꺼내면서 해당 노드와 연결된 노드들의 진입 차수를 감소시킨다.
4. 진입 차수가 0이 된 노드는 다시 큐에 삽입한다.
5. 큐가 빌 때까지 위 과정을 반복하면 위상 정렬 결과를 얻을 수 있다.

💻 코드 구현

from collections import deque

def topological_sort(n, edges):
    indegree = [0] * (n + 1)  # 진입 차수 배열
    graph = [[] for _ in range(n + 1)]  # 인접 리스트
    
    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1
    
    queue = deque()
    result = []
    
    # 진입 차수가 0인 노드 큐에 삽입
    for i in range(1, n + 1):
        if indegree[i] == 0:
            queue.append(i)
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for next_node in graph[node]:
            indegree[next_node] -= 1
            if indegree[next_node] == 0:
                queue.append(next_node)
    
    return result

# 예제 실행
n = 6
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (4, 6)]
print(topological_sort(n, edges))

🚀 위상 정렬의 활용

위상 정렬은 다양한 문제에서 활용된다.

1. 작업 스케줄링(Job Scheduling): 작업 간 선후 관계를 고려한 일정 정리
2. 컴파일러의 코드 빌드 순서 결정
3. 게임 캐릭터 스킬 트리 분석: 선행 스킬이 필요한 경우
4. 네트워크 패킷 처리 순서 결정

🔥 정리

• 위상 정렬은 DAG(방향 비순환 그래프)에서만 가능하다.
• 진입 차수를 이용한 BFS(Kahn’s Algorithm)와 DFS 기반 스택 방식이 있다.
• 다양한 순서를 가질 수 있으며, 작업 스케줄링 등 여러 분야에서 활용된다.