[알고리즘] 위상정렬 + 문제풀이

위상 정렬 => O(V+E)

• 순서가 정해져 있는 작업을 차례대로 수행할 때 사용되는 알고리즘 (방향그래프)
• 진입차수(indegree) : 노드로 들어오는 간선의 개수

1. 진입차수가 0인 것을 queue에 넣고 그 노드에서 출발하는 간선 삭제
2. queue가 빌 때까지 반복

코드

from collections import deque

v,e = map(int, input().split()) # v 노드 e 간선
indegree = [0] * (v+1) # 진입차수의 정보
graph = [[] for i 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: #진입차수가 0
      q.append(i)
  
  while q:
    now = q.popleft()
    result.append(now)

    for i in graph[now]:
      indegree[i] -= 1

      if indegree[i] == 0:
        q.append(i)

  for i in result:
    print(i, end=" ")

topology_sort()

 

관련 문제

14567 선수과목 O (골드4)

1005 ACM Craft

2252 줄 세우기

2623 음악프로그램

1766 문제집