백준 1766 문제집 파이썬
접근
위상 정렬을 이용해 현재 접근 가능한 수 중 가장 작은 값을 출력한다
- N 사이즈의 풀 수 있는 다음 문제가 담긴 2차원 리스트, 접근하기 위해 풀어야 하는 선행 문제의 갯수가 담긴 int 리스트를 선언한다.
- M 개의 조건문을 받고 A -> B 를 바라보도록 리스트에 추가해준다. B 의 선행문제 갯수는 하나 올라간다.
- 선행문제 카운트 리스트를 훑으며 지금 진입 가능한 (선행문제가 0인) 문제 번호들을 Priority Queue 에 넣는다.
- Priority Queue 에서 값을 뽑는다. 이 문제가 바라보는 다음 문제들을 훝으며 각각의 선행 문제 갯수를 하나씩 뺀다.
- 이 과정에서 선행 문제 갯수가 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) + " ")
