[BOJ] 음악프로그램

---

코드

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

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
indegree = [0]*(N+1)
for i in range(M):
    order = list(map(int, input().split()))
    for j in range(len(order)-1):
        if j == 0: continue
        graph[order[j]].append(order[j+1])
        indegree[order[j+1]] += 1

def topology_sort():
    result = []
    q = deque()
    for i in range(1, N+1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        v = q.popleft()
        result.append(v)
        for adj in graph[v]:
            indegree[adj] -= 1
            if indegree[adj] == 0:
                q.append(adj)

    for ind in indegree:
        if ind > 0:
            print(0)
            return

    for r in result: print(r)
    return

topology_sort()
        

결과

풀이 방법

• 위상정렬을 활용하는 문제이다.
• 큐가 비었을 때 진입차수가 0이 아닌 노드가 존재하면 사이클이 발생했다는 의미이므로 0을 출력한다.

---