[백준] 문제집 복기

문제

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

풀이

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


for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)  # 나가는 노드의 갯수 # 나중에 나가는 노드들의 들어오는 갯수를 줄여야 한다.
    in_cnt[b] += 1


li = []
for i in range(1,len(in_cnt)):
    if in_cnt[i] == 0:
        heapq.heappush(li,i)

res = []
while li:
    a = heapq.heappop(li)
    res.append(a)
    for v in graph[a]:
        in_cnt[v] -= 1
        if in_cnt[v] == 0:
            heapq.heappush(li,v)

print(*res)

heapq를 써야하는 문제였다.

힙을 쓰기 위해서

• li = [] 리스트를 만들고,

• append는
  heapq.heappush(li,item)

• 추출은
  heapq.heappop(li)