[알고리즘] 위상 정렬

위상 정렬(Topology Sort)의 정의

1. 순서가 정해져 있는 작업들을 순서를 유지시킨 상태에서 차례로 정렬하는 알고리즘.
2. 사이클이 없는 단방향 그래프의 요소를 순서대로 나열하되 방향성을 거스르지 않도록 정렬하는 알고리즘.

진입차수와 진출차수

위상정렬을 하는 과정에서 방향성을 거스르지 않도록 하는 요소는 진입차수와 진출차수이다.
진입차수는 특정 노드로 들어오는 Edge(간선)의 개수를 의미하며
진출차수는 특정 노드에서 나가는 Edge(간선)의 개수를 의미한다.
진입차수가 0인 노드는 앞의 차례가 없기 때문에 위상 정렬을 할 때 가장 먼저 정렬되는 대상이 된다.

위상정렬의 동작 과정

1. 해당 그래프의 요소 중 진입차수가 0인 요소를 큐에 삽입한다.
2. 해당 원소를 큐에서 제거하고 해당 노드의 진출차수에 해당하는 Edge를 모두 제거한다.
3. 해당 Edge가 모두 제거되어 진입차수가 0이 된 노드를 큐에 삽입한다.
4. 2번-> 3번을 큐가 빌 때까지 반복한다.

이렇게 동작하면 각 요소가 큐에 삽입되는 순서가 곧 위상정렬을 수행하였을 때 순서임을 확인할 수 있다.

위상정렬의 활용

해당 문제는 각 학생 2명의 키를 비교한 결과를 바탕으로 정렬하는 문제이다.
따라서 방향성을 거스르지 않는 선에서 차례대로 정렬하는 위상정렬을 활용하기 적절하다.

또한 위상정렬은 여러가지 답이 존재할 수 있다.
위상 정렬의 특징 중 하나인데, 동작과정에서 진입차수가 0이되어 0이 된 노드가 여러 개일 경우 큐에 들어가는 순서에 따라 정렬되는 순서도 바뀔 수 있기 때문이다.

이러한 특징을 생각하고 문제를 해결하면 된다.

import sys
from collections import deque, defaultdict
sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline

n, m = map(int, input().split())
# 입력 값 받기
graph = defaultdict(list)
# 그래프 초기화.
entry_order = {i: 0 for i in range(1, n+1)}
# 진입 차수 저장 딕셔너리 초기화

for _ in range(m):
    front, behind = map(int, input().split())
    graph[front].append(behind)
    # 그래프 요소 삽입
    entry_order[behind] += 1
    # 진입차수 1증가. front에서 진출한 간선이 behind와 연결되었기 때문.

order = []
# 위상정렬한 순서를 저장할 리스트 초기화

def Topological_Sorting():

    queue = deque()

    for i in range(1, n+1):
        if entry_order[i] == 0:
            queue.append(i)
	# 모든 요소를 확인하면서 진입차수가 0인 요소를 확인하여 큐에 삽입
    # 진입차수가 0이라는 것은 앞의 순서에 있는 요소가 없다는 것.
    
    while queue:
        number = queue.popleft()
		# 해당 숫자를 큐에서 제외한다.
        
        for i in graph[number]:
            entry_order[i] -= 1
            # 해당 요소와 연결되어 있는 간선도 사라짐.
            # 따라서 해당 요소와 연결되어 있는 요소들의 진입차수도 1감소
            if entry_order[i] == 0:
                queue.append(i)
			# 진입차수가 0이되면 큐에 삽입
        order.append(number)
		# 큐에 들어간 순서대로 위상정렬을 진행한다.
        
    print(*order)
    exit()


Topological_Sorting()