[Python] 음악프로그램 - 백준 (위상정렬)

해당 글은 백준 2623번 '음악프로그램' 문제를 다룬다.

문제

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

 

설명

해당 문제는 위상 정렬 알고리즘으로 해결할 수 있다.

m명의 PD가 정한 순서들을 모두 반영할 수 있는지 여부는 result 리스트의 갯수가 가수의 수(n)인지를 파악할 수 있다.

 

코드

from collections import deque

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

for _ in range(m):
    arr = list(map(int, input().split()))
    for i in range(1, len(arr)-1):
        graph[arr[i]].append(arr[i+1])
        indegree[arr[i+1]] += 1

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

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

if len(result) != n:
    print(0)
else:
    print('\n'.join(map(str, result)))