[Python] 백준 2623번 : 음악프로그램

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

2623번: 음악프로그램

---

문제 풀이

그래프 이론 중 위상정렬 문제이다.

 

위상정렬 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다.

느낀 점

위상정렬에 대해서 한번 짚고 넘어갈 수 있는 문제가 되었다.

코드

import sys
input = sys.stdin.readline

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

for _ in range(M):
    arr = list(map(int, input().split()))
    for s in range(1, arr[0]):
        graph[arr[s]].append(arr[s+1])
        indegree[arr[s+1]] += 1

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

while q:
    n = q.pop(0)
    ans.append(n)
    for i in graph[n]:
        indegree[i] -= 1

        if indegree[i] == 0:
            q.append(i)

if len(ans) != N: print(0)
else:
    for i in ans:
        print(i)