[백준 2623번] 음악프로그램 (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 pd in range(M):
  order = list(map(int,input().split()))
  for i in range(1,order[0]):
    x1,x2 = order[i],order[i+1]
    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)

if len(seq) == N:
  for i in range(N):
    print(seq[i])
else:
  print(0)

 

줄세우기 문제를 풀고나면 너무나 쉽게 풀 수 있는 문제. 다만 차이점이 있다면 사이클이 발생할 수 있다는건데, 이는 줄세우기한 리스트의 길이가 N인지, 즉 모든 원소가 빠져나왔는지만 확인하면 되는 문제이다.

 

 

오늘의 교훈) 알고리즘을 많이 알아야한다.