[PS] 백준#1766 문제집 / 파이썬

알고리즘 문제 풀이

• 문제 : 문제집
• 해결 : solved
• 분류 : 위상정렬, 우선순위큐

풀이 과정

1. 입력 차수를 배열에 저장한다. (자신의 노드로 화살표가 들어오는 횟수)
2. 차수가 0인 노드들을 힙에 push
3. while문을 순회하면서 pop된 node에 연결된 노드들의 차수를 검사한다.
4. 0인 차수들은 힙에 push, 현재 노드의 연결된 모든 노드들의 차수를 1씩 차감
5. 힙에서 꺼낸 순서대로 출력한다.

   힙에 있는 노드들은 모두 입력 차수가 0임이 보장된다.

소스코드

N, M = map(int, input().split())
degree =[0] * (N+1)
graph =[[] for _ in range(N+1)]

for i in range(M):
    prev, post = map(int, input().split())
    degree[post] += 1
    graph[prev].append(post)

import heapq

heap = []
for i in range(1, N+1):
    if degree[i] == 0:
        heap.append(i)

heapq.heapify(heap)

while heap:

    node = heapq.heappop(heap)
    print(node, end=' ')
    for n in graph[node]:
        degree[n] -= 1
        if degree[n] == 0 :
            heapq.heappush(heap, n)