python 백준 2623 음악 프로그램

백준 2623 음악 프로그램

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

2623번: 음악프로그램

문제 : 가수들의 음악 방송 순서 정하기

접근법

1. 피디들의 각자 방송 순서를 정해서 온다

2. 피디들의 방송 순서에 위반되지 않게 방송 순서를 정해야 한다 -> 위상 정렬

3. 위상정렬은 DAG형태일 때 가능하며 순환되는지 체크해줘야 된다. -> 방문 체크나 사라지지 않은 간선(edge)의 개수를 파악하여 확인

4. Dfs(stack) 와 Queue(in_degree)를 이용하는 방법중 queue를 이용하여 풀었다.

import sys
from collections import deque
sys.stdin = open('inputs.text')

n, pd = map(int,sys.stdin.readline().split())
in_degree = [0]*(n+1)
graph = [[] for _ in range(n+1)]
ans = []
## 간선의 개수와 인접리스트를 만들어줌 ##
for _ in range(pd):
    temp = list(map(int,sys.stdin.readline().split()))
    for i in range(1,len(temp)):
        in_degree[temp[i]] = in_degree[temp[i]] + len(temp[1:i])
        graph[temp[i]] = graph[temp[i]] + temp[i+1:]

queue = deque()
for i in range(1,n+1):
    if in_degree[i] == 0:
        queue.append(i)
## queue를 이용한 위상정렬 ##
while queue:
    node = queue.popleft()
    ans.append(node)
    for i in graph[node]:
        in_degree[i] -= 1
        if in_degree[i] == 0:
            queue.append(i)
## 정렬이 끝났는데 남아있는 간선의 개수가 남아있는 점(vertex)는 순서의 위반되는 애들 ##
for check in in_degree:
    if check > 0:
        print(0)
        exit()
for answer in ans:
    print(answer)