[백준] 1766번 문제집 - 파이썬

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

1766번: 문제집

import sys
from collections import deque
import heapq
n,m = map(int,sys.stdin.readline().split())
indegree = [0] * (n+1)
graph =[[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int,sys.stdin.readline().split())
    indegree[b] += 1
    graph[a].append(b)

def topology_sort():
    result =[]
    q= []

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

    while q:

        now = heapq.heappop(q)
        result.append(now)

        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] ==0:
                heapq.heappush(q,i)

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

topology_sort()

이 문제는 우선순위 큐

다익스트라에서 많이 사용하는 큐를 같이 사용해야 풀린다

위상 정렬에 우선 순위 큐까지 

문제의 조건에 맞게 풀면된다.

 

참고하면 좋은 문제

https://zoozoozoo.tistory.com/412

[백준] 14500번 줄 세우기(위상 정렬) - 파이썬

https://zoozoozoo.tistory.com/411

위상 정렬

개념

 

https://zoozoozoo.tistory.com/415

[백준] 1916번 최소비용 구하기 - 파이썬