이번 문제는 우선순위 큐, 즉 파이썬에서의 heapq 모듈을 이용하여 해결하였다. 처음 접근은 그래프를 저장할 때에 현재 문제보다 먼저 풀어야 되는 문제를 인접 리스트로 저장하고, 1부터 n까지 순회하며 현재 문제 번호보다 먼저 풀어야 하는 문제를 재귀 함수를 통해 찾았다. 답도 제대로 나왔지만 백준에 제출하였을 때 가차없이 오답 처리 되었다. 그래서 다른 접근 방법을 찾아보던 중 우선순위 큐로 접근하면 된다는 사실을 알게 되었다.

처음에 접근한 인접 리스트와 반대로 다음에 풀어야 할 문제에 대한 인접 리스트 형태로 저장해주고, 먼저 풀어야할 문제가 없는 문제 번호를 heapq에 넣어준다. 그리고 heapq가 존재하는 동안 반복하는 while문을 돌며 heapq에서 값을 추출하고 추출한 문제 다음에 풀어야 할 문제를 순회하며 값들을 heapq에 넣어주는 방식으로 접근하였다.

• n, m을 입력받는다.
• 다음에 풀 문제 번호를 저장할 인접 리스트 problem을 선언한다.
• 먼저 풀어야할 문제의 갯수를 저장할 리스트 prev_cnt를 n+1 크기로 선언하고 0으로 채운다.
• heapq로 사용할 q를 선언한다.
• 정답을 저장할 리스트 answer를 선언한다.
• m번 반복하는 for문을 돌린다.
  -> a, b를 입력받는다.
  -> problem[a]에 b를 넣는다.
  -> prev_cnt[b]를 1 증가시킨다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 만약 prev_cnt[i]가 0일 경우, i를 q에 넣어준다.
• q가 존재하는 동안 반복하는 while문을 돌린다.
  -> q에서 추출한 값을 cur로 선언한다.
  -> answer에 cur을 넣는다.
  -> problem[cur]을 순회하는 nxt에 대한 for문을 돌린다.
  --> prev_cnt[nxt]를 1 감소시킨다.
  --> 만약 prev_cnt[nxt]가 0일 경우,
  ---> q에 nxt를 넣는다.
• answer를 언팩킹하여 출력한다.

Code

import heapq
n, m=map(int, input().split())
problem=[[] for _ in range(n+1)]
prev_cnt=[0 for _ in range(n+1)]
q=[]
answer=[]
for _ in range(m):
    a, b=map(int, input().split())
    problem[a].append(b)
    prev_cnt[b]+=1
for i in range(1, n+1):
    if prev_cnt[i]==0:
        heapq.heappush(q, i)
while q:
    cur=heapq.heappop(q)
    answer.append(cur)
    for nxt in problem[cur]:
        prev_cnt[nxt]-=1
        if prev_cnt[nxt]==0:
            heapq.heappush(q, nxt)
print(*answer)