[백준 2623번] 파이썬 - 음악프로그램

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

2623번: 음악프로그램

 

 

# 조건

• 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다.
• 순서를 정하기 위해서는 많은 조건을 따져야 한다.
• 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다.
• 보조 PD들이 가져온 것은 아래와 같다.
  • 1 4 3
  • 6 2 5 4
  • 2 3
  • 첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다.
  • 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다.
  • 한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 정했다.
• 남일이가 할 일은 이 순서들을 모아서 전체 가수의 순서를 정하는 것이다.
• 남일이는 잠시 생각을 하더니 6 2 1 5 4 3으로 순서를 정했다. 이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다.
• 물론, 1 6 2 5 4 3으로 전체 순서를 정해도 괜찮다.
• 경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다.
• 예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다.
• 이번에 남일이는 우리 나라의 월드컵 4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다.
• 이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.
• 보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수의 순서를 정하는 프로그램을 작성하시오.

 

# 접근 방법

• 위상 정렬을 이용하여 풀어준다.
• 입력을 받으며 PD 내 다음의 가수를 기록해준다.
• 또한, degree 리스트의 다음 가수 차수를 +1 해준다.
• 차수가 0인 가수들을 que에 넣어준 후 탐색해준다.
• 이 때, 위상정렬의 경우 DAG (비순환 방향 그래프)에서만 정점을 선형으로 정렬하는 것이다.
  • 따라서, 사이클이 존재하는지 검사해주어야 하는데
  • 위상정렬을 시킨 ans의 길이가 노드의 개수 이하인 경우 0을 출력해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
N, M = map(int, input().split())  
singer = [[] for _ in range(N+1)]  
degree = [0] * (N+1)  
  
for i in range(M):  
    lst = list(map(int, input().split()))  
    for s in range(1, lst[0]):  
        singer[lst[s]].append(lst[s+1]) #노드(s) -> 노드(s+1)  
        degree[lst[s+1]] += 1  
        
que = deque()  
for i in range(1, N+1):  
    if degree[i] == 0:  
        que.append(i)  
  
result = []  
while que:  
    node = que.popleft()  
    result.append(node)  
    for j in singer[node]:  
        degree[j] -= 1  
        if degree[j] == 0:  
            que.append(j)  
  
if len(result) != N:  
    print(0)  
else:  
    print(*result, sep='\n')