프로그래밍/Python
[Python] 백준 1766 문제집
모영이
2021. 3. 10. 15:01
1766번: 문제집
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주
www.acmicpc.net
위상정렬 : 위상정렬에 우선순위 큐를 사용해야 한다. 파이썬은 힙큐가 있기 때문에 너무 쉽다. 하지만 좀 막막할 수가 있다. 힙큐 쓰는 것을 솔직히 알고리즘 분류 클릭해보고 나서 알았다.
전체코드
import sys
import heapq
import collections
input = sys.stdin.readline
N, M = map(int, input().split())
inDegree = [0 for _ in range(N + 1)]
graph = collections.defaultdict(list)
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B)
inDegree[B] += 1
heap = []
for i in range(1, N + 1):
if inDegree[i] == 0:
heapq.heappush(heap, i)
result = []
while heap:
node = heapq.heappop(heap)
result.append(node)
for i in graph[node]:
inDegree[i] -= 1
if inDegree[i] == 0:
heapq.heappush(heap, i)
print(*result)