[백준 파이썬] 1766 문제집

백준 1766

가능하면 쉬운 문제부터 풀되 먼저 풀어야하는 문제는 먼저 풀어야한다.
선행되어야 하는 작업이 있고, 쉬운 문제부터 풀어야 하므로 힙을 이용해 위상 정렬로 풀었다.

import heapq

N, M = map(int, input().split())
order = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N+1)] # idx 위치에 문제를 풀어야 다음 문제를 풀 수 있음
in_order = [0 for _ in range(N+1)] # 진입 차수, idx 번째 문제를 풀기 위해 풀어야하는 문제 수
visited = [False for _ in range(N+1)] # 방문 여

for first, then in order:
    heapq.heappush(graph[first], then) # 쉬운 문제부터 다음에 풀 문제 추가
    in_order[then] += 1

ans = []
q = []
for i, val in enumerate(in_order[1:], 1):
    if val == 0: # 먼저 풀어야 할 문제가 존재하지 않는다면
        heapq.heappush(q, i) # 푼 문제에 추가
        visited[i] = True # 방문 처리, 같은 문제가 반복되서 들어와 진입 차수가 감소되는 것 방지

while q:
    v = heapq.heappop(q) # 쉬운 문제부터
    ans.append(v) # 푼 문제에 추가
    for _ in range(len(graph[v])): # 다음에 풀 수 있는 문제 개수 동안
        next_v = heapq.heappop(graph[v]) # 다음으로 쉬운 문제
        if not visited[next_v] or in_order[next_v] >= 1: # 처음 본 문제거나 먼저 풀어야 할 문제가 있다면
            visited[next_v] = True # 방문 표시
            in_order[next_v] -= 1 # 먼저 풀어야할 문제 하나 해결
            if in_order[next_v] == 0: # 모두 풀었다면
                heapq.heappush(q, next_v) # 푼 문제에 추가
print(*ans)