[정글 WEEK03_알고리즘] 개발 일지 - 위상 정렬

정의

DAG(Directed Acyclic Graph, 방향 비순환 그래프)에서 노드 간 선후 관계를 방향성에 거스르지 않고 나열하는 정렬 기법

 

출처: https://namu.wiki/w/%EC%9C%84%EC%83%81%20%EC%A0%95%EB%A0%AC

 

사용 예시

 - 작업 순서 설정

 - 선수 과목 고려한 학습 순서

 - 빌드 시스템(컴파일 순서)

 - 스케줄링 문제 등

 

핵심 개념

 - 진입 차수(In-degree)

   : 특정 노드로 들어오는 간선의 수

 

 

수행 절차

1. 모든 노드의 진입 차수 계산
2. 진입 차수가 0인 노드를 큐에 삽입
3. 큐가 빌 때까지 아래 과정 반복

        3-1) 큐에서 노드를 꺼내 결과 리스트에 추가

        3-2) 해당 노드에서 나가는 간선 제거(연결된 노드의 진입 차수 -1)

        3-3) 새롭게 진입 차수가 0이 된 노드를 큐에 삽입

 

사이클 판별

 - 모든 노드를 방문하기 전에 큐가 비면 → 사이클 존재

 - 즉, V개의 노드를 방문하지 못한 채 큐가 비는 경우, 위상 정렬 불가능 (순환 구조가 있기 때문)

 

시간 복잡도

 - O(V + E)
   → 모든 노드(V)와 간선(E)을 한 번씩 확인하므로

 

 

구현

1. 큐를 활용한 BFS 방식의 Kahn's Algorithm

 - deque를 이용해서 레벨 순서대로 처리

 - 진입 차수가 0인 노드들을 동시에 관리하여 순서 제어

 - 먼저 진입 차수가 0이 된 노드부터 넓게 탐색

 - 진입 차수로 사이클 판별

from collections import deque

v, e = map(int, input().split())
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]

# 방향 그래프의 모든 간선 정보
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b) # 정점 A에서 B로 이동
    indegree[b] += 1 # 진입차수를 1 증가
    
def topology_sort():
    result = []
    q = deque()
    
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)
    
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    
    for i in result:
        print(i, end=" ")
  
  topology_sort()

 

 

2. 스택을 활용한 DFS 방식

 - 후위 순회(post-order) 로 처리하고, 스택에 노드를 넣어서 나중에 꺼내는 방식

 - DFS 기반은 간접적으로 순서를 보장

 - 사이클 판별을 위해 방문 중 → 방문 완료 체크 필요

import sys
sys.setrecursionlimit(10**6) # 재귀 호출 깊이 제한 늘림

def dfs(node, visited, graph, stack):
    visited[node] = True
    for next_node in graph[node]:
        if not visited[next_node]:
            dfs(next_node, visited, graph, stack)
    stack.append(node)  # 후위 순회 방식으로 스택에 push

def topology_sort_dfs(V, edges):
    graph = [[] for _ in range(V + 1)]
    visited = [False] * (V + 1)
    stack = []

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

    # 모든 노드에 대해 DFS 실행
    for i in range(1, V + 1):
        if not visited[i]:
            dfs(i, visited, graph, stack)

    # 스택에 쌓인 순서를 뒤집어서 출력
    return stack[::-1]  # 위상 정렬 결과