백준 1766번: 문제집 (Python)

접근

문제집을 풀 때 먼저 풀어야 하는 문제가 있다는 점에서 위상 정렬 알고리즘을 이용하고, 풀 수 있는 문제 중에서 가장 난이도가 쉬운 문제, 즉 가장 숫자가 작은 문제 먼저 푼다는 점을 추가적으로 고려해주면 풀 수 있다.

위상 정렬 알고리즘은 단계별 문제를 풀면서 앞선 문제들을 풀면서 익숙해질 수 있었다.

위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python)

백준 2252번: 줄 세우기 (Python)

추가적인 고려를 해주지 않고 기본 위상 정렬 알고리즘으로만 푼다면, 예제에서 주어진 경우를 봤을 때, 다음과 같이 오답이 나오게 된다.

1. 1번은 3번 이후에 2번은 4번 이후에 풀 수 있으므로 in_degree 가 각각 1이고, 3번과 4번는 in_degree 가 0의 값을 가진다.
2. 즉, 초기에 in_degree 리스트를 순환하며 in_degree 가 0인 경우를 탐색하여 queue 에 추가할 때, 3번 다음으로는 4번이 추가 되게 된다.
3. 3번을 푼 후에는 1번과 4번을 풀 수 있는데, 1번이 아닌 4번을 먼저 풀게 되므로 오답이 발생한다.

이를 해결해주기 위해서는 queue를 계속적으로 sort 하여 현재 풀 수 있는 문제 중 가장 작은 문제를 먼저 푸는 방법도 있지만, 현재 queue 중에서 가장 작은 값만 의미가 있으므로 빠른 계산을 위해 최소 heap 알고리즘을 이용하기로 하였다.

heappush 및 heappop 함수를 직접 구현하지 않고 heapq 라이브러리를 불러와 풀어보았다.

heap 알고리즘 및 heapq 라이브러리 사용: 2021.04.06 - [코딩/백준 (Python)] - 백준 1655번: 가운데를 말해요 (Python)

백준 1655번: 가운데를 말해요 (Python)

코드

import sys
import heapq

n, m = map(int, sys.stdin.readline().split())
tree = [[] for _ in range(n + 1)]
in_degree = [0] * (n + 1)
heap = []
result = []
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    in_degree[b] += 1
    tree[a].append(b)
for i in range(1, n + 1):
    if in_degree[i] == 0:
        heapq.heappush(heap, i)
while heap:
    now = heapq.heappop(heap)
    result.append(now)
    for i in tree[now]:
        in_degree[i] -= 1
        if in_degree[i] == 0:
            heapq.heappush(heap, i)
print(*result)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!