Baekjoon 1766. 문제집 / Python

1766. 문제집

난이도 : 골드 2
소요 시간 : 20분
날짜 : 2024.12.26
언어 : 파이썬
알고리즘 유형 : 위상정렬, 방향 비순환 그래프, 우선순위 큐, 그래프

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. n개의 문제를 모두 풀어야 한다.
2. 문제 번호가 낮으면 더 쉬운 문제이다.
3. 쉬운 문제를 먼저 풀어야 한다.
4. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.

2. 해결 방식

1. 위상정렬과 우선순위큐를 활용하여 해결한다.
2. 먼저 해결해야하는 문제가 주어졌다 == 위상정렬
3. 쉬운문제(번호가 낮은 문제)를 먼저 풀어야 한다 == 우선순위 큐
   • 그냥 큐를 사용해서 푸는 위상정렬 문제에서 큐를 우선순위 큐로 바꾸면 해결된다.
   • 문제 번호 낮은게 먼저 풀어야 하기 때문에, 그냥 우선순위 큐에 문제 번호를 넣어서 위상정렬을 하면 끝!

3. 정답 코드

import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

# input = sys.stdin.readline

from collections import defaultdict
from heapq import heappop, heappush

n, m = map(int, input().split())
orders = [0] * (n + 1)    # orders[i] = 먼저 풀어야 할 문제 개수(몇 문제를 풀어야 i번문제를 풀 수 있는가)
arr = defaultdict(list)    # arr[i] = 후에 풀어야 할 문제 개수(i번 문제를 풀어야만 풀 수 있는 문제들 리스트)

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

q = []
for i in range(1, n + 1):
    if orders[i] == 0:
        heappush(q, i)    # 먼저 풀어야 하는 문제가 없는 애들만 q에 넣기

res = ''

while q:
    now = heappop(q)
    res += str(now) + ' '    # 결과를 바로 문자열로 저장하기
    for next in arr[now]:    
        orders[next] -= 1    # 먼저 풀 게 하나 줄었다.
        if orders[next] == 0:    # 먼저 풀 게 없어졌다면 q에 넣기
            heappush(q, next)

print(res)