위상 정렬(Topological Sort)이란?

위상 정렬은 사이클이 없는 방향 그래프의 정점들을 방향성을 거스르지 않고 순서대로 나열하는 것을 의미한다.

정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.

 

 

위 그림과 같이 수강해야 할 과목이 세 가지 있다고 가정하자. 세 과목을 정상적으로 수강하기 위해서는 화살표의 방향대로

[자료구조 - 알고리즘 - 고급 알고리즘] 순으로 들어야 한다. 만약 [자료구조 - 고급 알고리즘 - 알고리즘] 순으로 듣고자 한다면, 해당 순서는 화살표의 방향을 거스르기 때문에 올바른 수강 순서가 아니다. 

 

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

진입차수(Indegree)는 특정한 정점으로 들어오는 간선의 개수를 의미하며, 진출차수(Outdegree)는 특정한 정점에서 나가는

간선의 개수를 의미한다.

 

위상 정렬 알고리즘의 동작 과정은 아래와 같다.

1. 초기 진입차수가 0인 정점을 큐에 넣는다.
2. 큐가 빌 때까지 아래의 과정을 반복한다.
3. 큐에서 원소를 꺼내 해당 정점과 연결된 정점의 진입차수를 줄여준다.
4. 새롭게 진입차수가 0이 된 정점을 큐에 삽입한다.

정점	1	2	3	4	5	6	7
진입차수	0	1	1	2	1	2	1
큐	1
결과	-

 

정점	1	2	3	4	5	6	7
진입차수	0	0	1	2	0	2	1
큐	2, 5
결과	1

 

정점	1	2	3	4	5	6	7
진입차수	0	0	0	2	0	1	1
큐	5, 3
결과	1, 2

 

정점	1	2	3	4	5	6	7
진입차수	0	0	0	1	0	0	1
큐	3, 6
결과	1, 2, 5

 

정점	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	1
큐	6, 4
결과	1, 2, 5, 3

 

정점	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	0
큐	4, 7
결과	1, 2, 5, 3, 6

 

정점	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	0
큐	7
결과	1, 2, 5, 3, 6, 4

 

정점	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	0
큐	-
결과	1, 2, 5, 3, 6, 4, 7

import sys
from collections import deque

input = sys.stdin.readline
# 노드의 개수와 간선의 개수 입력
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
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)

    # 위상 정렬 수행한 결과 출력
    for res in result:
        print(res, end=' ')


topology_sort()

# sample input
# 7 8
# 1 2
# 1 5
# 2 3
# 2 6
# 3 4
# 4 7
# 5 6
# 6 4