[알고리즘] 위상 정렬(Topology Sort)

 

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

#삽입하면서 우선순위 설정
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    degree[b] += 1

#우선순위가 제일 높은거만 푸시
for i in range(1, n+1):
    if degree[i] == 0:
        heapq.heappush(q, i)

answer = []
while q:
    temp = heapq.heappop(q)
    answer.append(temp) #우선순위가 높은거중에 제일 쉬운문제부터 정답에 푸시
    for i in graph[temp]: #해당 문제 다음 우선순위애들 순회하면서 우선순위 감소시킴
        degree[i] -= 1
        if degree[i] == 0:
            heapq.heappush(q, i)

print(*answer)

 

사이클이 없는 방향그래프(DAG) 에서 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 정해주는 알고리즘.

 

 

참고 문제

2252번: 줄 세우기

1766번: 문제집