[알고리즘] 위상 정렬 (Topological Sorting)

 

위상 정렬 (Topological Sorting)이란?

• 정렬 알고리즘의 일종으로, 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.
• 사이클이 없는 방향 그래프(DAG)의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미한다.

 

예시

그림과 같이 총 3개의 과목이 있다고 가정하자.
세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야한다.
만약 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다.

 

진입차수와 진출차수

위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 

• 진입차수 (Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수 (Outdegree) : 특정한 노드에서 나가는 간선의 개수

위상 정렬 알고리즘 동작 과정

1. 정점들의 Indegree, indeg[1...N] 계산하기 
2. 진입차수가 0(indeg[i] == 0)인 노드를 큐에 넣는다.
3. 큐가 빌 때까지 다음의 과정을 반복한다.
    1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
    2) 새롭게 진입차수가 0이 된 노드를 큐에 삽입 

 

위상 정렬 알고리즘은 보통 큐를 이용하여 구현한다.

각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과이다.

 

시간 복잡도

O(v + E)

 

위상 정렬의 특징

• 위상 정렬은 사이클이 없는 방향 그래프 (DAG)에 대해서만 수행할 수 있다.
  ※ DAG (Direct Acyclic Graph) : 순환하지 않는(=사이클이 없는) 방향 그래프
• 위상 정렬에서는 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재할 수 있다는 의미이다.
• 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다. 왜냐하면 사이클에 포함된 원소 중에서 해당되는 어떠한 원소도 큐에 들어가지 못하게 되기 때문이다.
• 보통 큐로 구현하나, 스택을 이용한 DFS를 이용해 위상 정렬을 구현할 수도 있다.

 

위상 정렬 파이썬 코드

import sys
from collections import deque

input = sys.stdin.readline

v, e = map(int, input().split())

indegree = [0] * (v + 1) # 모든 노드에 대한 진입차수는 0으로 초기화

graph = [[] for _ in range(v + 1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 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)
        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for g in graph[now]:
            indegree[g] -= 1
            if indegree[g] == 0:
                q.append(g)

 

백준 문제 예시

• 백준 2252번 - 즐 세우기
• 백준 2623번 - 음악 프로그램
• 백준 9470번 - Strahler 순서
• 백준 14676번 - 영우는 사기꾼?
• 백준 1005번 - ACM Craft
• 백준 1516번 - 게임 개발
• 백준 2056번 - 작업
• 백준 2637번 - 장난감 조립

 

참고 문헌

https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting

[알고리즘] 위상 정렬 (Topological Sorting)