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

문제 링크: https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

 

 

---

문제 풀이

위상 정렬 기본 문제이다. 위상 정렬로 처리해서 결과 리스트의 길이가 n보다 작은 경우 0을 출력하고 n인 경우 하나씩 출력하면 된다.

 

 

코드

	from collections import deque
	import sys
	input = sys.stdin.readline
	n, m = map(int, input().split())
	indegree = [0] * (n+1)
	graph = [[] for _ in range(n+1)]
	for _ in range(m):
	array = list(map(int, input().split()))
	for i in range(2, len(array)):
	a, b = array[i-1], array[i]
	graph[a].append(b)
	indegree[b] += 1
	result = []
	q = deque()
	for i in range(1, n+1):
	if indegree[i] == 0:
	q.append(i)
	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:
	for i in result:
	print(i)
	else:
	print(0)

view raw 2623.py hosted with ❤ by GitHub