[BOJ/백준] 1766. 문제집 (Python)

🔎 문제

🔗 백준 1766번 문제집

💡 풀이

위상정렬 로 푸는 문제인데, 조건에 가능하면 쉬운 문제부터 풀어야 한다. 가 추가된 것이 특징이다.

기존 위상정렬로 푸는 문제인 🔗 백준 2252번 줄 세우기와 다르게 딱 한가지만 더 추가하면 된다.

1. 진입차수에 대한 배열을 만든다.
2. 진입차수를 초기화 한다.
3. 진입차수가 0인 노드를 큐에 넣는다.
4. 큐에서 ❗❗가장 작은❗❗노드를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. (이 과정에서 간선을 따라 다다른 노드의 진입차수를 1씩 감소시킨다)
5. 새롭게 진입차수가 0이 된 노드들을 큐에 넣는다.
6. 3~5번을 큐가 빌 때까지 반복한다.

4번 ‘가장 작은’노드를 꺼내는 것이 핵심인데, 필자는 초기에

node = min(Q)
Q.remove(node)

이런 방법으로 시간 초과를 맛봤다.

더 좋은 방법도 있겠지만 (있으면 알려주세요..!!!💖) 어떻게 하면 시간을 줄일까 생각 하다가 최소힙이 생각이 났다.

파이썬의 내장 함수 min()은 시간복잡도가 O(N) 이고, heapq 모듈을 이용한 heapq.heappop()은 O(logN)이다. 최소힙을 쓰면 시간초과 없이 통과가 된다. 전체 소스코드는 아래에 첨부했다.

📃 소스코드

import sys
import collections
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
graph = collections.defaultdict(list)
indegree = [0] * (n + 1) # 진입 차수 테이블

result = []
Q = []

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
    
for i in range(1, n + 1):
    if indegree[i] == 0:
        heapq.heappush(Q, i)

while Q:
    node = heapq.heappop(Q)
    result.append(node)
    for _next in graph[node]:
        indegree[_next] -= 1
        if indegree[_next] == 0:
            heapq.heappush(Q, _next)

print(*result)

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️