위상정렬(Topological Sorting)

이번 시간에는 위상 정렬에 대한 개념과 동작 과정을 알아본다. 이후 위상 정렬을 Python으로 구현해 본다. 

1. 위상 정렬(Topological Sorting)

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

 

1-1. 예시 - 선수과목을 고려한 학습 순서 설정

그림과 같이 총 3개의 과목이 있다고 가정하자.

세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야 한다.

만약 알고리즘 -> 자료구조 -> 고급 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다.

 

1-2. 진입 차수(Indegree)란?

위상 정렬을 학습하기 전에 먼저 진입 차수를 알아야 한다.

💡 특정한 노드로 들어오는 간선의 개수를 의미한다.

위 예시에서는

• 자료구조: 0 개
• 알고리즘: 1 개
• 고급 알고리즘: 2 개

 

 

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

여기서는 큐를 이용한다.

1. 진입 차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 아래 과정 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2. 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다.

⇒ 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다

 

2-1. 위상 정렬 동작 예시

아래 그림을 통해 동작 과정을 이해해보자.

 

[step 0] 진입 차수가 0인 모든 노드를 큐에 삽입. 현재 1번 노드의 진입 차수만 0이므로 큐에 1번 노드만 삽입하게 된다.

우선 진입 차수를 노드별 세팅을 모두 한다. 그 이후 0인 진입 차수를 찾아서 큐에 넣어준다.

[step 1] 큐에 있는 1번 노드를 꺼낸다. 이후 1번 노드와 연결되어 있는 간선들을 제거한다. 그러면 2번 노드와 5번 노드의 진입 차수가 0이 되고, 2번 노드와 5번 노드의 진입 차수가 0이므로 큐에 삽입한다.

[step 2] 큐에 있는 2번 노드를 꺼낸다. 2번 노드와 연결되어 있는 간선들을 제거한다. 그러면 3번 노드의 진입 차수가 0이 되므로 3번 노드를 큐에 삽입한다.

[step 3] 큐에 있는 5번 노드를 꺼낸다. 5번 노드와 연결되어 있는 간선들을 제거한다. 그러면 6번 노드의 진입 차수가 0이 되므로 6번 노드를 큐에 삽입한다.

 

[step 4] 큐에 있는 3번 노드를 꺼낸다. 3번 노드와 연결되어 있는 간선들을 제거한다. 이번 단계에서는 새롭게 진입 차수가 0이 되는 노드가 없으므로 넘어간다.

[step 5] 큐에 있는 6번 노드를 꺼낸다. 6번 노드와 연결되어 있는 간선들을 제거한다. 그러면 4번 노드의 진입차수가 0이 되므로 4번 노드를 큐에 삽입한다.

[step 6] 큐에 있는 4번 노드를 꺼낸다. 4번 노드와 연결되어 있는 간선들을 제거한다. 그러면 7번 노드의 진입차수가 0이 되므로 7번 노드를 큐에 삽입한다.

 

 

3. 위상 정렬의 특징

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

 

 

4. 구현하기 (Python)

💡 위상 정렬 문제는 아래 코드를 베이스로 일부만 변경하여 문제 풀 수 있다.

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 아래 과정 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

"""
[입력]
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
[출력]
1 2 5 3 6 4 7
"""
from collections import deque
import sys

def topology_sort():
    result = []
    q = deque()
    # 1. 진입차수가 0인 모든 노드를 큐에 넣는다.
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)
        # 2. 큐가 빌 때까지 아래 과정 반복한다.
    while q:
        # 2-1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            # 2-2. 새롭게 진입차수가 0이된 노드를 큐에 넣는다.
            if indegree[i] == 0:
                q.append(i)
    # 3. 위상 순서 출력
    for i in result:
        print(i, end=' ')

v, e = map(int, sys.stdin.readline().split())  # 노드 수, 간선 수

indegree = [0] * (v + 1)  # 진입차수
graph = [[] for i in range(v + 1)]  # 선후 관계

# 1. 초기세팅 - 선후 관계, 진입 차수 세팅
for _ in range(e):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)  # a > b
    indegree[b] += 1  # 진입 차수

# 2. 위상정렬 진행
topology_sort()

 

 

5. 위상 정렬 시간 복잡도

시간 복잡도는 O(V+E) 위상 정렬을 수행할 때, 

1. 차례대로 모든 노드를 확인하면서 O(V)

2. 해당 노드에서 출발하는 간선을 차례대로 제거 O(E) 해야 한다.

=> 따라서 노드와 간선을 모두 확인하는 것을 고려하여 O(V) + O(E) = O(V+E)의 시간이 소요된다.

 

 

 

6. 위상 정렬(Topological Sort)과 관련된 문제 유형 

1, 2번 유형은 필수 유형 문제이니 꼭 풀어보기!  ✍️

1.   큐를 이용한 위상 정렬
   • 선수과목 - 백준 14567
   • 줄 세우기 - 백준 2252
2. 우선순위 큐를 이용한 위상 정렬
   • 문제집 - 백준 1766
3. 여러 위상 순서 중 가장 짧게 걸리는 위상 정렬 방법 구하기
   • 작업 - 백준 2056
   • 게임 개발 - 백준 1516

 

 

참고

• '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책