[BOJ] 위상 정렬 Basic

📚 Topological Sort

출처 : https://www.acmicpc.net/problem/2252

❓ 위상 정렬

• 순서가 정해져 있는 작업을 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘
• 사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열한 것

🧐 Directed Acyclic Graph (DAG)

사이클이 없는 방향 그래프로, DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용한다.

💡 풀이

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
inDegree = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
result = []

for _ in range(m):
    a, b = map(int, input().split())
    inDegree[b] += 1
    graph[a].append(b)

queue = deque()
for i in range(1, n + 1):
    if inDegree[i] == 0:
        queue.append(i)

while queue:
    x = queue.popleft()
    result.append(x)
    for i in graph[x]:
        inDegree[i] -= 1
        if inDegree[i] == 0:
            queue.append(i)
            
print(*result)

📝 해설

각 노드의 진입 차수를 구한다.

• 각 노드의 진입 차수는 해당 노드로 들어오는 간선의 수 를 의미한다.
• e.g. a -> b 간선이 존재하면 리스트 inDegree의 b 요소의 값을 증가시킨다.

진입 차수가 0인 노드를 덱에 삽입한다.

• BFS 알고리즘을 사용하여 순서대로 탐색하기 위해 시작점을 정하는 과정이라고 생각하면 된다.

아래의 과정을 통해 덱에서 나오는 순서대로 노드들이 정렬된다.

1. 덱의 왼쪽에 있는 노드를 순서대로 꺼낸다.
2. 덱에서 꺼낸 노드에서 다른 노드로 향하는 간선이 있다면, 다른 노드의 진입 차수를 감소시킨다.
3. 다른 노드의 진입 차수가 0이 되었다면, 덱에 삽입한다.
4. 위의 과정을 반복한다.