백준 1766 문제집

문제 링크: 1766 문제집

문제 분석:
N개의 문제는 모두 풀어야 한다.
먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
가능하면 쉬운 문제부터 풀어야 한다.
쉬운 문제는 번호가 빠른 문제이다.

import sys; input = lambda: sys.stdin.readline().rstrip()
import heapq
from collections import deque

N, M = map(int, input().split()) # 문제지, 정보의 개수
lst = []
for _ in range(M):
    lst.append(tuple(map(int, input().split())))
# 정렬 하면 앞에꺼 부터 위상정렬이 되지 않을 까 했던 과거의 나.. 
lst.sort()

graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)
for i in range(M):
    a, b = lst[i][0], lst[i][1]
    graph[a].append(b)
    indegree[b] += 1 # 진입 차수 1 추가

result = []
q = []
# 힙큐 사용.. 알고리즘 태그 고마워.. 
for i in range(1, N+1):
    if not indegree[i]:
        heapq.heappush(q, i)
while q:
    now = heapq.heappop(q)
    result.append(now)
    for j in graph[now]:
        indegree[j] -= 1
        if not indegree[j]:
            heapq.heappush(q, j)

print(*result)