[BOJ] 백준 1766번: 문제집

1일 1PS 19일차!

📚 문제

---

골드 2

• 입력받는 줄의 수가 많기 때문에 sys 를 사용해 입력 받는 것을 추천한다.

• 입력 예시

  • 1 -> 3 -> 5
  • 2 -> 4 -> 5
  • 위와 같이 관계를 띄고 있을 경우
    • 1. [1, 2] 중에서 가장 낮은 번호 result 에 추가, result = []
    • 1. [3, 2] 중에서 가장 낮은 번호, result = [1, ]
    • 1. [3, 4] 중에서 가장 낮은 번호, result = [1, 2]

  • 계속 추가되는 번호들 중에서 가장 낮은 번호를 뽑아내야하기 때문에 minHeap 을 사용해야한다.

  • 가장 낮은 번호를 고르는 리스트에 추가되는 것들은 자신의 선수 문제들이 현재 존재하지 않는 경우이다. 즉 선수 문제들의 수를 저장해놓아야한다.

💡 포인트

---

1. Graph 에 i 번째 문제를 풀어야 풀이가 가능한 문제를 Graph[i] 에 저장한다.
2. i 번째 문제를 풀기 위해 우선적으로 풀어야할 문제의 수를 preSolved[i] 에 저장한다.
3. preSolved[i] == 0 인 경우 가장 낮은 번호를 뽑기 위한 minHeap 에 추가한다.
4. minHeap 에서 가장 낮은 번호를 result 에 저장하고 해당 문제가 선수 문제인 문제들의 preSolved[i] -= 1 하고, 0 이 되면 minHeap 에 추가한다.

💻 코드

---

import sys
import heapq

n, m = map(int, input().split())

result = []
graph = [[] for _ in range(n + 1)]
preSolved = [0 for _ in range(n+1)]
minHeap = []


for i in range(m):
    pre, post = map(int, sys.stdin.readline().rstrip().split())
    graph[pre].append(post)
    preSolved[post] += 1

for i in range(1, n + 1):
    if preSolved[i] == 0:
        heapq.heappush(minHeap, i)

while minHeap:
    tmp = heapq.heappop(minHeap)
    result.append(tmp)
    for i in graph[tmp]:
        preSolved[i] -= 1
        if preSolved[i] == 0:
            heapq.heappush(minHeap, i)


print(" ".join(map(str, result)))