[Python] 위상정렬 - JuyeolRyu/CodingTest GitHub Wiki

1. 위상 정렬(Topological Sort)

  • 일의 순서를 찾는 알고리즘
  • 방향 그래프에서 탐색 순서를 찾을 때 사용된다.
  • 위상 정렬의 결과는 그래프 탐색 순서대로 정렬된다.
    image

2. 위상 정렬(Topological Sort) 예시

#필요 라이브러리
import sys
from collections import deque
from collections import defaultdict
#그래프와 위상이 저장될 딕셔너리
dic = defaultdict(list)
degree = defaultdict(int)
#탐색부
while q:
    cur = q.popleft()
    ans.append(cur)
    for ne in dic[cur]:
      degree[ne] -= 1
      if degree[ne] == 0:
        q.append(ne)

3. 위상 정렬(Topological Sort) 문제

  1. 입력
  2. graph 딕셔너리에 현재 노드와 연결된 다음 노드들을 저장
  3. indegree 딕셔너리에는 현재 노드의 위상을 저장 (=> 현재 노드에 오기 위해 필요한 노드의 개수)
  4. 탐색 방법은 BFS로 이루어진다.
  5. 그래프를 탐색할 때 위상이 0이면 탐색 시작이 가능하므로 큐에 넣는다.
  6. dp 딕셔너리에는 각각의 노드를 방문하기 위한 비용이 저장된다.
  7. 만약 큐에서 뺀 노드의 번호가 목표 노드라면 비용을 리턴한다.
  8. 목표 노드가 아니라면 현재 노드와 연결된 노드의 위상을 줄여주고 dp 값을 경신한다.
  9. 만약 다음 노드의 위상이 0이라면 큐에 넣어준다.