♟ 위상 정렬

관련글 :

그래프 (위상 정렬 관련 문제 언급)	https://waydd.tistory.com/15
Kahn 흐름 참고 (문제 풀이 절차)	https://waydd.tistory.com/11

 

 

1. 위상 정렬 (Topological Sort)

 

방향성이 있는 그래프(Directed Acyclic Graph, DAG) 에서 모든 노드(정점)들을 순서대로 나열하는 방법

( 그래프 기반, 정점 순서를 정하는 알고리즘 )

※ 단, 이 순서는 모든 간선 (u → v)에 대해 u가 v보다 먼저 나와야 하는 조건을 만족 (+ 사이클도 없어야함)

※ 1→2→…→N = 토폴로지 순서

• 어떤 노드 A에서 B로 향하는 간선이 있다면, 정렬된 순서에서 A가 B보다 앞에 오도록 함
  →→ 작업의 순서를 정하는 문제 ( 전체 작업을 순서대로 수행 시, 어떤 순서로 해야 할지를 결정 )
• 간선의 방향은 선수 → 후수
  → 이러한 선후 관계 (간선 방향) 가 모이면 전체 작업의 흐름이 생김, 이를 정렬한 것
  ※ 선후수 개념 : 작업이나 사건들 간에 정해진 순서가 있을 때, 먼저(先) 와 나중(後) 의 관계
• 가능한 해가 유일하지 않은 경우가 많음 (부분 순서만 주어짐, 나머지는 자유)
  (예시) 1→2, 1→3 → [1,2,3]도 정답, [1,3,2]도 정답 (2와 3의 상대적 순서는 자유)
• 큐(BFS 기반, Kahn) 또는 스택(DFS 기반)으로 구현 가능 (그래프의 진입 차수 배열 등을 활용)
  → 진입 차수 0인 정점부터 탐색 시작하여 큐 삽입 vs DFS 종료 후 스택 삽입
  → 입력 : 방향 비순환 그래프(DAG)
  → 출력 : 정점의 순서 (모든 간선 (u → v)에서 u가 v보다 먼저 나옴)
• 시간 복잡도 : O(V + E) (정점 수 V, 간선 수 E)
• 작업 스케줄링, 컴파일 순서, 빌드 순서 등에 사용 :

※ 진입 차수가 0 인 노드가 하나도 없다면 사이클이 존재함을 의미할 수 있음

 

 

2. 코드 구현

 

- (공통) 입력 : 노드 수 (노드는 0에서 n-1까지), 인접리스트 (노드 u에서 나가는 노드들의 리스트)

n = 6
graph = [
    [2, 3],  # 0 → 2, 3
    [3, 4],  # 1 → 3, 4
    [5],     # 2 → 5
    [5],     # 3 → 5
    [],      # 4
    []       # 5
]

 

 

- Kahn’s Algorithm (BFS 기반)

• 진입 차수(indegree)를 이용해 순서를 하나씩 결정
• 진입 차수 배열 + 큐 활용 레벨 순회 ( 진입 차수가 0일때 큐 삽입 )
  → 전처리 : 각 정점의 진입차수를 계산
  → 진입차수가 0인 정점은 그래프 내에서 앞에 올 것이 없는 정점, 순서에 포함 가능 ⭕
• deque 사용 : 큐 연산 빠르게 처리 (pop/append가 O(1))
• 모든 노드의 진입 차수를 계산 후 진입 차수가 0인 노드를 큐에 넣음 (선수가 없는 작업 = 가장 먼저 수행 가능한 노드)
  → 큐에서 꺼낸 노드를 결과에 추가하고, 그 노드에서 나가는 간선을 제거
  → 그로 인해 진입 차수가 0이 된 노드를 큐에 추가
  → 위를 반복하여 정렬된 순서 획득 (위상 정렬 완성)
• 정렬된 노드 수가 전체 노드 수와 다르면 사이클이 존재

from collections import deque

def topological_sort_bfs(n, graph):
    indegree = [0] * n  # 각 노드의 진입 차수(자신에게 들어오는 간선의 수)
    for u in range(n):  
        for v in graph[u]:    # 모든 간선을 돌면서 진입 차수 배열을 채웁
            indegree[v] += 1  # u → v 라면, v의 진입 차수를 1 증가

    # 진입 차수가 0인 노드들을 큐에 미리 넣음 
    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)  # 선수 조건이 모두 충족되어 처리 가능한 노드
        
        # u에서 나가는 간선을 모두 제거
        for v in graph[u]:
            indegree[v] -= 1  # 간선 제거하면 연결된 노드의 진입 차수 줄이기
            if indegree[v] == 0:  # 진입 차수가 0이 되면 그 노드를 큐에 넣음
                queue.append(v)

    if len(result) != n:
        return []  # 사이클 존재
    return result

 

 

- DFS 기반 위상정렬 (재귀 방식)

• 재귀 기반 후위 순회 + 스택 활용 ( DFS 끝난 순서대로 삽입 + 결과 역순 )
• 노드 u 를 방문 표시한 뒤, 그 노드에서 나가는 모든 노드 v에 대해 재귀적으로 호출
  → 즉, 방문하지 않은 노드에서 DFS 수행 반복  ( 연결되지 않은 컴포넌트도 정렬에 포함되기 위함 )
  → 이후 모든 자식 노드를 방문한 뒤(깊이 끝까지) 자기 자신을 추가 (후위 순회 방식)
  → 모든 DFS가 끝난 뒤 스택을 뒤집으면 위상 정렬 결과
• 사이클 탐지는 별도 로직이 필요함
  → visited 외에 탐색 중인 상태(1) 를 따로 추적하는 배열이 필요

# DFS 위상 정렬
def topological_sort_dfs(n, graph):
    visited = [False] * n  # 각 노드 방문 체크
    result = []

    def dfs(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs(v)
        result.append(u)

    for i in range(n):
        if not visited[i]:
            dfs(i)

    result.reverse()
    return result

# 개선된 DFS 위상 정렬 (사이클 탐지 추가)
def topological_sort_dfs_with_cycle(n, graph):
    visited = [0] * n  # 0: 미방문, 1: 탐색 중, 2: 탐색 완료
    result = []
    is_cycle = False

    def dfs(u):
        nonlocal is_cycle
        if visited[u] == 1:
            is_cycle = True
            return
        if visited[u] == 2:
            return

        visited[u] = 1  # 탐색 중
        for v in graph[u]:
            dfs(v)
        visited[u] = 2  # 탐색 완료
        result.append(u)

    for i in range(n):
        if visited[i] == 0:
            dfs(i)

    if is_cycle:
        return []  # 사이클이 있으므로 위상 정렬 불가
    return result[::-1]

 

 

 

3. 검증 및 예외 처리

 

- 방문 수 기반 사이클 판정

• 위상정렬이 끝난 뒤, 큐에서 꺼낸(또는 결과 리스트에 담긴) 노드의 개수
• 왜 방문 수로 사이클을 알 수 있는지
  → Kahn 알고리즘에서 매 단계 진입차수 0인 노드만 제거됨 = 사이클 내부 노드는 끝내 진입차수가 0이 되지 않음
  → 큐에서 꺼낼 수 있는 총 노드 수가 n 에 미달
• visited_cnt == n  : 모든 노드를 방문(정렬) 완료 → 사이클 없음
• visited_cnt != n  또는 visited_cnt < n : 일부 노드가 정렬되지 못함 → 사이클 존재

※ 사이클 판정 표기 선택
- != n  은 모든 노드를 방문하지 못했다 라는 의미 (사이클 여부 판정 전용)
- < n  는 정량적 해석 포함, 실질적 의미는 동일
-  != n  이 의도 가 더 직접적, 주로 쓰임

 

 

- 관련 예외 + 간선 케이스 정리

• 자기 루프(self-loop) 가 있는 노드 : 시작부터 그 노드는 큐에 들어오지 않음 → visited_count < n 케이스
• 분리된 컴포넌트 : 사이클이 없더라도 모든 컴포넌트를 시작점으로 처리하면 visited_count == n 성립
  (시작점 선택 누락 조심)
• 다중 간선/중복 간선 : 진입차수 계산 시, 중복 반영 유의 (사이클 판정에는 영향 없음, 구현상 버그 원인 가능성)
• 입력 N=0 또는 간선 없는 그래프 : visited_count == n