백준 1766: 문제집 (Python)

 

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

1766번: 문제집

 

위상정렬을 이용해서 풀면 되는데

'먼저 푸는 것이 좋은 문제'에 대한 정보를 간선으로 저장하고

가능하면 쉬운 문제를 먼저 풀어야 하는데 난이도는 1번~n번 차례대로 되어 있으니

큐를 오름차순으로 정렬해서 쓰면 된다. -> 우선순위 큐 사용함

 

# 우선순위큐
from queue import PriorityQueue

# 생성
q = PriorityQueue()
q = PriorityQueue(maxsize = 8)  # 최대 크기 8

# 원소 추가
q.put(1)
# 원소 삭제
q.get()

# 큐의 사이즈를 반환
q.qsize()
# 큐가 비어있으면 True, 비어있지 않으면 False 반환
q.empty()
# 큐가 가득 차있으면 True, 그렇지 않으면 False 반환
q.full()

 

from queue import PriorityQueue
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

info = [[] for _ in range(n+1)]
indegree = [0] * (n+1)

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

q = PriorityQueue()
res = []

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

while q.empty() is False:
    now = q.get()
    res.append(now)
    for i in info[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            q.put(i)

for i in res:
    print(i, end=' ')