[알고리즘/파이썬] 백준 2623 - 음악프로그램

문제

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

2623번: 음악프로그램

 

풀이

저번에 2252 - 줄 세우기 문제에서 위상정렬에 대해 공부했었는데 이 문제도 위상정렬 문제여서 반가웠다. ㅎ

이쯤되면 클래스 5가 전부 다 그래프 문제인가 싶은..^ _ ^ . . .

 

위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 이다.

위상 정렬 문제의 특징 중 하나는 답안이 여러개일 수 있다는 점이다.

진입차수가 0인 노드를 어느 순서로 넣느냐에 따라 답이 달라질 수 있다.

 

이 문제는 보조 피디들의 무대 순서를 모두 그래프와 진입차수에 기록해두고 찾아가는 방식이고, result 값이 n이 아니면 중간에 사이클이 생김(보조 피디의 순서들 간에 모순ㅇ ㅣ생김) 으로 판단하고 0을 출력하는 식으로 해주었다.

 

 

코드

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

n,m = map(int,input().split())

graph = [[] for _ in range(n+1)]
indegree = [0 for _ in range(n+1)]

result = []

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

    while q:
        x = q.popleft()
        result.append(x)

        for next in graph[x]:
            indegree[next] -= 1
            
            if indegree[next] == 0:
                q.append(next)

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

topological_sort()
    
if len(result) != n:
    print(0)
else:
    for i in result:
        print(i)