[백준 2252번] 줄 세우기 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N,M = map(int,input().split())

indegree = [0]*(N+1)
child = [[] for i in range(N+1)]
for i in range(M):
  x1,x2 = map(int,input().split())
  child[x1].append(x2)
  indegree[x2] += 1

dq = deque()
for i in range(1,N+1):
  if indegree[i] == 0:
    dq.append(i)
seq = []

while dq:
  x = dq.popleft()
  for i in child[x]:
    indegree[i] -= 1
    if indegree[i] == 0:
      dq.append(i)
  seq.append(x)

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

 

도저히 풀이방법이 안떠올라서 며칠을 묵혀놨던 문제.

위상정렬 알고리즘으로 푸는 문제라고 해서 결국 위상정렬에 대해서 읽어보고 구현할 수 있었다.

 

위상정렬 알고리즘의 가장 핵심은 진입차수이다. 진입차수(indegree)가 0인 것들만 골라서 줄을 세우면 된다.

 

진입차수라는 개념에 대해서 배울 수 있었던 좋은 문제였다

 

 

오늘의 교훈) 위상정렬 문제들을 풀어보자