문제

[백준] 문제집 (Gold 2)

요약

  • 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 먼저 푼다.
  • 가능하면 쉬운 문제부터 푼다.
  • 풀 문제의 순서를 결정하자.

분류

  • 위상 정렬
  • 우선순위 큐

풀이

1. 내 풀이 (위상 정렬)

  • 간단하게 말하면, 위상정렬에서 쓰이는 큐를 우선순위 큐로 대체하기만 하면 된다. 진입차수가 같은 노드 간의 순서(=난이도)만 결정하면 되기 때문이다.


import sys
from heapq import heappop, heappush
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
cnts = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    cnts[b - 1] += 1

queue = []

for i in range(n):
    if cnts[i] == 0:
        heappush(queue, i)

ans = []

while queue:
    cur = heappop(queue)
    ans.append(cur + 1)

    for i in graph[cur]:
        cnts[i] -= 1

        if cnts[i] == 0:
            heappush(queue, i)
print(*ans)