알고리즘 | 그래프 탐색 | 위상 정렬(Topological Sort)

위상 정렬은 방향 그래프(Directed Graph)에서 노드를 정렬하는 방법이다. u -> v 방향을 갖는 각 간선 (u, v)에 대해서, u가 v보다 앞에 오도록 정렬한다.

 

여러가지 작업이 주어지고, 특정 작업이 특정 작업보다 선행되어야 한다는 순서 조건이 달렸을 때, 전체 순서를 어떻게 전개해야할 것인가와 관련하여 탁월한 답을 내려준다. 이러한 특성 덕에, 위상 정렬은 프로젝트를 스케줄링할 때, 작업 우선순위 지정 등 다양한 분야에서 활용된다. 

 

---

기본 개념

• 의존성(Dependency): A 작업이 B 작업에 의존한다는 것은, A 작업이 시작하기 전에 B 작업이 완료되어야 함을 의미한다.
• 진입차수(in-degree): 한 노드로 들어오는 간선의 수
• 진출차수(out-degree): 한 노드에서 나가는 간선의 수 

 

위상 정렬 알고리즘 구현

위상 정렬을 구현하는 방법은 크게 큐를 이용하는 방법과 스택, DFS를 함께 이용하는 방법이 있다. 

 

큐를 이용한 방법 vs 스택과 DFS를 이용한 방법

	큐를 사용하는 방식 (Kahn's Algorithm)	스택과 DFS를 사용하는 방식
구현 난이도	직관적이고 구현하기 쉽다.	복잡하며 재귀를 사용한다.
시간 복잡도	O(V+E)	O(V+E)
싸이클 감지 및 처리	싸이클이 없을 때만 작동하며, 싸이클 존재를 쉽게 확인한다.	싸이클이 있으면 작동하지 않으며, 싸이클 감지에 추가 로직이 필요하다.
성능	일반적으로 빠르다.	재귀 호출의 오버헤드로 인해 느릴 수 있다.
추천 상황	구현의 간단함과 싸이클 감지의 용이성을 중시할 때	특정 문제의 문맥이나 개인의 기술 수준에 따라 더 적합할 수 있다.

큐를 이용한 방법이 더욱 직관적이며, 시간 복잡도 측면에서도 큰 차이가 없다. 따라서 이를 우선적으로 학습한다. 

 

큐를 이용한 방법을 kahn 알고리즘이라고 부른다. 

 

 

kahn's Algorithm

동작 과정

칸 알고리즘은 큐를 활용하는 위상 정렬 알고리즘으로, 동작 과정은 다음과 같다.

1. indegree가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음 과정을 반복적으로 수행한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2. 새롭게 indegree가 0이 된 노드를 큐에 넣는다.
   => 결과적으로, '각 노드가 큐에 들어온 순서 == 위상 정렬을 수행한 결과'가 된다.

 

위상 정렬 특징 (Kahn 알고리즘 기준)

1. 위상 정렬은 DAG에 대해서만 수행할 수 있다.
   • DAG(Direct Acyclic Graph): 비순환 방향 그래프
2. 위상 정렬은 여러가지 답이 존재할 수 있다.
   • 그래프의 구조와 초기 노드의 선택에 따라, 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상이 된다면 분기점이 나뉘게 된다.
3. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
   • 사이클에 포함된 원소 중에서 어떤 원소도 큐에 들어가지 못한다.

 

코드로 이해하기

아래는 kahn 알고리즘을 구현한 예시.

from collections import deque

# 노드 개수와 간선 개수 입력받기
V, E = map(int,input().split())
# 모든 노드에 대한 indegree 배열 초기화
indegree = [0]*(V+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(V+1)]

# 방향 그래프의 모든 간선 정보 입력받기
for i in range(E):
    x, y = map(int, input().split())
    graph[x].append(y) # 정점 x -> y 방향으로 이동 가능
    indegree[y] += 1 # y의 indegree 값 1 증가

# 위상 정렬 함수
def kahn(graph):
    result = [] # 정렬 수행 결과를 담을 리스트
    que = deque() # 큐 세팅

    # 1. indegree가 0인 모든 노드를 큐에 넣는다.
    for i in range(1, V+1):
        if indegree[i] == 0:
            que.append(i)
    
    # 2. 큐가 빌 때까지 다음 과정을 반복적으로 수행한다.
    while que:
        # 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
        current = que.popleft() # 큐에서 원소 꺼내기
        result.append(current) # 결과에 추가      
        
        for i in graph[current]: # 현재 노드가 가리키는 노드들에 대해 
            indegree[i] -= 1 # indegree 값 1 감소
            
            # 2) 새롭게 indegree가 0이 된 노드를 큐에 넣는다. 
            if indegree[i] == 0:
                que.append(i)
        
    return result



### 결과 출력 ###
result = kahn(graph)
for i in result:
    print(i, end=' ')

 

코드 내용이 직관적이라, 알고리즘 동작 과정만 이해했다면 무리없이 이해할 수 있다. 

중간중간 print()를 찍어보면 대략적인 과정을 확인할 수 있다.

 

좌측: 입력, 우측: print 찍어보기

 

 

이를 실제 문제에 적용시켜보자. (백준 2252번 '줄 세우기') (https://www.acmicpc.net/problem/2252)

문제:
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력:
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.학생들의 번호는 1번부터 N번이다.

출력:
첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

문제 이해:
1. 두 학생간에는 순서(방향)가 주어진다. (N = 학생 = 노드, M = 키를 비교한 횟수 = 간선의 수)
2. 키 비교라는 특성상 사이클이 형성될 수 없다. -> DAG 조건 충족

# 문제: 줄 세우기 (골드 3)
import sys
input = sys.stdin.readline
from collections import deque

V, E = map(int, input().split())

indegree = [0 for i in range(V+1)] # 각 노드의 indegree 정보 -> 0으로 초기화
graph = [[] for i in range(V+1)] # 간선 정보를 담기 위한 배열

for i in range(E):
    A, B = map(int, input().split())
    graph[A].append(B) # A 학생 키 < B 학생 키 (줄 순서: A -> B)
    indegree[B] += 1

def topological_sort(graph):
    que = deque()
    result = []

    # indegree가 0인 학생 담기
    for student in range(1, V+1): 
        if indegree[student] == 0:
            que.append(student)

    # 큐가 빌 때까지
    while que:
        # 큐에서 하나씩 빼면서, 해당 학생과 연결된 간선 제거        
        current = que.popleft()
        result.append(current)

        for friend in graph[current]:
            indegree[friend] -= 1

            if indegree[friend] == 0:
                que.append(friend)

    return result

### 출력 부분 ###
result = topological_sort(graph)
for i in result:
    print(i, end=' ')

 

 

 

---

참고자료

https://www.youtube.com/watch?v=xeSz3pROPS8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=36