[백준][자료구조/힙] 1766.문제집 (파이썬/Python)

import sys
import heapq

n,m = map(int,input().split())
B_list = [[] for _ in range(n+1)]
check = [0 for _ in range(n+1)]
heap = []
answer = []

for _ in range(m):
    a,b = map(int,input().split())
    B_list[a].append(b)
    check[b] += 1

for i in range(1,n+1):
    if check[i] == 0:
        heapq.heappush(heap,i)

while heap:
    now = heapq.heappop(heap)
    answer.append(now)
    for i in B_list[now]:
        check[i] -= 1
        if check[i] == 0:
            heapq.heappush(heap,i)

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

 

 

[나름의 해석]

• 조금 헷갈렸던 부분은 heap을 사용하면 최소힙을 기준으로 계속 아래부분부터 갈텐데? 했었다 그런데 answer라는 답만 출력해주기 위해 만든 리스트를 사용하면 이를 쉽게 해결이 가능했다 .
• A > B 순서로 나와야 하기에 이를 고려해주어야 했다.
• B_list : B에 해당하는 수들을 따로 담아주는 리스트를 만들어 넣어주고 (후에 사용하기 위해서) 
• check : 말 그대로 본인의 앞에 수가 있어야 하는지를 판별하기 위해 만든 리스트 앞에 우선으로 나가야 하는 수가 있던 수라면 이를 표시해 놓는다.(후에 사용하기 위해)
• heap : B_list에 들어가지 않은 수라면 최소 힙으로 정렬해서 넣어준다.
• heap에 있는 수 중에 가장 우선순위가 빠른 것들을 꺼내가며 하나씩 확인해주며 answer 리스트에 넣어 진행해준다.