[Python]파이썬 - 문제집(백준 1766) #위상정렬/힙

baekjoon 문제- https://www.acmicpc.net/problem/1766

파이썬: 문제풀이 (위상정렬) - 백준

필요한 알고리즘 - 위상정렬, 힙(heap)

1. 진입 차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 해당 원소와 간선을 제거한다.
3. 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.
4. 큐가 비어질 때까지 2)번과 3)번을 반복한다.

입력 - 첫째줄 총 문제수 N개, 정보 2개
4 2 
4 2
3 1


import heapq

n, m = map(int, input().split())
array = [[] for i in range(n+1)]

indegree = [0] * (n+1)
heap = []

for _ in range(m):      
    x, y = map(int, input().split())
    array[x].append(y)              # x:3 -> y:1, 4->2
    indegree[y] += 1                # 1node(1), 2node(2) in degree

for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)   #  heap(q) save <-- node 3 and node 4  

result = []

while heap:
    data = heapq.heappop(heap)         # 큐에서 원소를 꺼냄
    result.append(data)                # result에 저장
    for y in array[data]:           
        indegree[y] -= 1               # 큐에서 꺼낸 원소의 간선을 제거
        if indegree[y] == 0:    
            heapq.heappush(heap, y)    # 진입차수가 0이 된 정점을 큐에 삽입
            
for i in result:
    print(i, end=' ')