[Python]위상정렬 백준 1766

   문제

   https://www.acmicpc.net/problem/1766

위상정렬읠 하는것은 동일하다. 위상정렬의 특성상 따라 여러가지 출력값을 가질수 있다.

 이 문제는 한가지 값만 나올수 있도록 조건이 있다.

쉬운 문제를 먼저 즉 진입차수가 0일때도 순서가 있다.

최소힙을 이용하여 가장 쉬운(문제 번호가 작은) 문제부터 출력 할수 있도록 해주면 된다.

import sys
import heapq
 
N,M=map(int,sys.stdin.readline().split())
tree=[[] for _ in range(N+1)]
inDegree=[0 for _ in range(N+1)]
 
 
q=[]
#문제 순서
for _ in range(M):
    a,b=map(int,sys.stdin.readline().split())
    tree[a].append(b)
    inDegree[b]+=1
 
#진입차수가 0이면 큐에 넣기
for i in range(1,N+1):
    if inDegree[i]==0:
        heapq.heappush(q,i)
 
#위상정렬
result=[]
while q:
    a=heapq.heappop(q)#최소힙 사용
    result.append(a)
    for i in tree[a]:
        inDegree[i]-=1
        if inDegree[i]==0:
            heapq.heappush(q,i)
 
print(*result)