[백준] 1766 문제집

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

어떤 문제들을 풀어야만 다음 문제를 풀 수 있으므로 위상 정렬을 이용하여 풀이하였습니다.

 

처음 문제를 접하였을 때, 세번째 조건인 쉬운 문제부터 풀어야 한다는 조건을 만족시키기 위하여 한문제를 풀이하고 문제 번호가 낮은 문제부터 다시 탐색하며 풀이를 진행하였습니다.

그러나 반복문을 이용하여 계속해서 앞쪽 문제부터 순서대로 탐색을 진행하여 불필요한 탐색이 많아졌고 시간초과가 발생하였습니다.

 

시간을 단축하기 위하여 한 문제를 풀이하고 계속 처음 앞쪽 문제부터 탐색을 진행하는 것이 아니라 최소힙을 이용하여 먼저 풀어야하는 문제를 다 푼 경우 최소힙에 추가하였습니다.

이로 인하여 가장 쉬운 문제부터 푸는 조건을 만족시키며 시간 단축이 가능했습니다.

2) 알고리즘

• 최소 힙
• 위상정렬

3) 풀이 코드

사용 언어 - Python

import sys
import heapq as h
sys.stdin = open('input.txt')

N, M = map(int, sys.stdin.readline().split())           # 문제의 수, 문제 정보의 개수
linked = [[] for _ in range(N+1)]                       # 각 문제별 가능한 다음 문제 리스트
need_solve = [0 for _ in range(N+1)]                    # 각 문제별 먼저 풀어야하는 문제의 개수
answer = []

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())       # 먼저 푸는 문제, 나중에 풀 문제
    linked[a].append(b)                                 # a 문제를 풀어야, b 풀수 있으므로 리스트에 추가
    need_solve[b] += 1                                  # 먼저 풀어야하는 개수 증가 

heap = []                                   # 바로 풀 수 있는 문제 리스트
for idx in range(1, N+1):                   
    if not need_solve[idx]:                 # 바로 풀 수 있다면
        h.heappush(heap, idx)               # 최소 힙에 추가

while heap:
    node = h.heappop(heap)
    answer.append(node)                     # 지금 풀 수 있으므로 정답에 추가

    for next in linked[node]:               # 이 문제를 풀었으므로 풀 수 있는 다음 문제들
        need_solve[next] -= 1               # 다음 문제에서 먼저 풀어야하는 문제의 개수 감소

        if not need_solve[next]:            # 다음 문제를 이제 풀 수 있으면 최소힙에 추가
            h.heappush(heap, next)

print(*answer)

---

🔗 문제 링크

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

1766번: 문제집

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다