접근

위상 정렬을 이용해 현재 접근 가능한 수 중 가장 작은 값을 출력한다

  1. N 사이즈의 풀 수 있는 다음 문제가 담긴 2차원 리스트, 접근하기 위해 풀어야 하는 선행 문제의 갯수가 담긴 int 리스트를 선언한다.
  2. M 개의 조건문을 받고 A -> B 를 바라보도록 리스트에 추가해준다. B 의 선행문제 갯수는 하나 올라간다.
  3. 선행문제 카운트 리스트를 훑으며 지금 진입 가능한 (선행문제가 0인) 문제 번호들을 Priority Queue 에 넣는다.
  4. Priority Queue 에서 값을 뽑는다. 이 문제가 바라보는 다음 문제들을 훝으며 각각의 선행 문제 갯수를 하나씩 뺀다.
  5. 이 과정에서 선행 문제 갯수가 0이 된 문제들을 Queue 에 추가해준다.

사고

혹시나 나처럼 헷갈리는 이들이 있을까 싶어 문제 조건을 확실히 해두고 싶다.

M 중에 2 1 6 1 이런 조건이 있다면 2, 6을 순서대로 해결하고 1로 돌아오는 것이 아니라 매 순간 접근 할 수 있는 (선행 문제가 풀려 있는) 문제 중 번호가 가장 작은 순서를 출력하면 된다.

참고: 백준 질문 게시판

import sys
from queue import PriorityQueue
input = sys.stdin.readline
N, M = list(map(int, input().split()))

graph = [[] for _ in range(N + 1)]
prev_link_cnt = [0] * (N + 1)

for _ in range(M):
    a, b = list(map(int, input().strip().split()))
    graph[a].append(b)
    prev_link_cnt[b] += 1

q = PriorityQueue()

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

while(q.qsize() > 0):
    c = q.get()
    for item in graph[c]:
        prev_link_cnt[item] -= 1
        if prev_link_cnt[item] == 0:
            q.put(item)
    sys.stdout.write(str(c) + " ")

submission