[Python] 위상 정렬(topology sort)

🔍 위상 정렬

대학교 전공 시간에 교수님이 전공 선수과목 구조를 예로 들어주셨던 것이 어렴풋이 기억난다..
핵심 이론과 구현 방법을 간단히 정리해 보려 한다.

Do it! 알고리즘 코딩테스트 도서를 참고하였다.

---

📃 개념

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
항상 유일한 값으로 정렬되지는 않음!

진입 차수 = 자기 자신을 가리키는 에지의 개수

1. 진입 차수 리스트를 업데이트한다.
2. 진입 차수 리스트 중 진입 차수가 0인 노드를 선택하여 정렬 리스트에 저장한다.
3. 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
4. 모든 노드가 정렬될 때까지 2 ~ 3 과정을 반복한다.

항상 유일한 값으로 정렬되지 않는 이유 => 2번 과정에서 진입 차수가 0인 노드가 여러 개 존재할 수 있기 때문에

---

🐍 코드

# ex) n = 5인 예시
# 1 -> 2, 3  
# 2 -> 4, 5  
# 3 -> 4  
# 4 -> 5  
# 5  

...

graph = [[] for _ in range(n + 1)] # 방향 그래프
indegree = [0 for _ in range(n + 1)] # 진입 차수 리스트

for ...:
   ...
   graph[a].append(b) # 방향 그래프 표현
   indegree[b] += 1 # 진입 차수 데이터 저장

queue = deque()

# 진입 차수가 0인 노드를 선택하여 덱에 저장
for i in range(1, n + 1):
   if indegree[i] == 0:
      queue.append(i)

# 위상 정렬 수행
while queue:
   now = queue.popleft()

   for next in graph[now]:
      indegree[next] -= 1 # 진입 차수 -1
      if indegree[next] == 0: # 진입 차수가 0이라면 덱에 저장
         queue.append(next)      

---