[백준]1766 문제집(Python)

https://www.acmicpc.net/problem/1766

1766번: 문제집

 

문제 접근

 

선행 문제를 풀어야 후행 문제를 풀 수 있다는 점에서 위상정렬 알고리즘을 사용해야한다.

하지만 답이 여러 개인 경우에는 아무거나 출력한다는 조건이 없기에 정답은 하나이다.

이 문제의 조건에서는 "가능한 쉬운 문제부터 풀어야 한다"라는 조건이 있다.

 

코드

from collections import deque
import sys
import heapq

input = sys.stdin.readline

# 문제 수, 순서 정보의 개수
n, m = map(int, input().split())

# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (n+1)

# 각 노드에 연결된 간선 정보를 담기 위한 그래프 초기화
graph = [[] for i in range(n+1)]

# 방향 그래프의 모든 간선 정보 입력
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # a -> b
    # 진입차수 1 증가
    indegree[b] += 1

hp = []
# 처음 시작할 때는 진입차수가 0인 노드를 우선순위 큐에 삽입(1부터 v까지 체크)
for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(hp, i)


while hp:
    now = heapq.heappop(hp)
    print(now, end = " ")
    # now와 연결된 노드들의 진입차수-1
    for i in graph[now]:
        indegree[i] -= 1
        # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
        if indegree[i] == 0:
            heapq.heappush(hp, i)

 

문제 회고

 

기존의 위상정렬 문제와 다르게 가능한 앞 번호의 문제부터 푸는 것이 유리하다는 조건이 있기에 우선순위 큐(heapq)를 이용하는 것이 생소했다.