[백준/boj] 1766: 문제집 (Python) / 위상정렬

• 문제링크: https://www.acmicpc.net/problem/1766

 

풀이

import sys
input = sys.stdin.readline
import heapq

n, m = map(int, input().split())
tree = [[] for _ in range(n+1)]
inDegree = [0 for _ in range(n+1)]

for _ in range(m):
  a, b = map(int, input().split())
  tree[a].append(b)
  inDegree[b] += 1

q = []
for i in range(1,n+1):
  if inDegree[i] == 0: # 차수가 0 인 문제를 최소 힙에 push
    heapq.heappush(q, i)

result = []
while q:
  a = heapq.heappop(q)
  result.append(a)
  for i in tree[a]: # 문제쌍 B가 있는 경우에
    inDegree[i] -= 1 # 문제쌍 B의 차수를 1 줄이고
    if inDegree[i] == 0: # 문제쌍 B의 차수가 0 이면
      heapq.heappush(q, i) # 최소힙에 push

print(*result) # *result(*args) : 가변 위치인자 (임의 개수의 위치 인자를 tuple 형태의 변수로 저장)

위상 정렬을 새롭게 배우게 됐다. 위상 정렬에서 필요한 것은 tree, inDegree 이다.

• tree는 n 개의 배열로 이루어져 있고, A번 문제를 먼저 풀어야 풀 수 있는 문제 B를 tree[A]에 append 한다.
• inDegree는 n개의 0으로 이루어져 있고, 먼저 풀어야되는 문제가 있는 문제들에 + 1 을 해준다. //  inDegree[i] : i를 풀기 전에 먼저 풀어야 되는 문제 수 

1. a 문제를 풀어야 b를 풀수 있다. → tree[a].append(b)
2. b 문제는 앞에 한 문제 더 (a) 풀어야 풀 수 있다. → inDegree[n] += 1
3. 진입차수(나를 풀기 전에 풀어야하는 문제)가 0이면 최소힙(쉬운 문제부터 풀기위한 자료구조)에 push
4. 위상 정렬 start (q가 빌때까지 반복)
   1. 문제 하나(A) pop (q에 있는 문제 중 가장 쉬운 문제)
   2. result 에 A를 add
   3. A를 풀었으니까, 이제 A를 풀고나면 풀 수 있는 문제들을 살펴보자 → for i in tree[a]
   4. A를 풀었으니까, 진입차수 하나 줄여줄게! → inDegree[i] -= 1
   5. 진입차수가 0이네? 너 이제 풀어도 되겠다 → heapq.heappush(q, i)

 

위상 정렬을 모르고 풀었을 때 시간 초과가 나서 다른 풀이를 참고 했다. (출처: https://developmentdiary.tistory.com/466)

위상 정렬의 개념은 아래 블로그를 보면 자세하게 나와있다.

https://m.blog.naver.com/ndb796/221236874984