[백준][Python] 2633 음악프로그램

문제해결에 선행또는 후행 하는 순서가 있으면 위상정렬을 이용하면 쉽게 풀 수 있다.

위상정렬이란 위상이 0 즉 앞뒤에 뭐가 없는 node부터 위로 찬찬히 쌓아 나가는 것.
위상0인 문제를 해결했으면 그 바로 연결된 노드들의 위상을 1씩 낮추면서 계산해 나간다.

나는 배열에 쌓기 위해서 앞에 나와야 하는 노드를 위상0으로 두었지만

반대로 뒤가 없는 노드들을 먼저 쌓고 역순으로 출력할 수도 있을 것이다.

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

def topological_sorting():
    queue = deque()
    for i in range(1, N+1):
        if level[i] == 0: 
            queue.append(i)
    while queue:
        cur_order = queue.popleft()
        final_order.append(cur_order)
        for post_order in post_order_table[cur_order]:
            level[post_order] -= 1
            if level[post_order] == 0:
                queue.append(post_order)

N, M = map(int, input().split())
level = [0 for _ in range(N+1)]
post_order_table = defaultdict(list)
final_order = []

for _ in range(M):
    order = list(map(int, input().split()))
    for i in range(1,len(order) - 1): 
        post_order_table[order[i]] += [order[i+1]]
        level[order[i+1]] += 1

topological_sorting()

if len(final_order) != N:
    print(0)
    exit()

for singer in final_order:
    print(singer)