백준 2623 음악프로그램
문제
https://www.acmicpc.net/problem/2623
코드
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
in_degree = [0]*(n+1)
for i in range(m):
temp = list(map(int, input().split()))
for j in range(2, temp[0]+1):
graph[temp[j-1]].append(temp[j])
in_degree[temp[j]] += 1
q = deque()
for i in range(1, n+1):
if in_degree[i] == 0:
q.append(i)
answer = []
while q:
now = q.popleft()
answer.append(now)
for i in graph[now]:
in_degree[i] -= 1
if in_degree[i] == 0:
q.append(i)
if len(answer)==n:
for i in answer:
print(i)
else:
print(0)
풀이
위상정렬 문제다!
가수들을 그래프의 노드로 생각하고, 입력으로 주어지는 출연 가수의 순서를 단방향성 간선으로 연결해주면 싸이클이 없는 단방향성 그래프가 완성된다 예제 입력의 경우
for i in range(m):
temp = list(map(int, input().split()))
for j in range(2, temp[0]+1):
graph[temp[j-1]].append(temp[j])
in_degree[temp[j]] += 1
# graph [[], [4], [5, 3], [], [3], [4], [2]]
# in_degree [0, 0, 1, 2, 2, 1, 0]
이렇게 graph와 in_degree가 완성되고 여기서 in_degree는 index의 노드가 몇개의 노드들에게 연결 당했는지(?) 를 나타낸다
in_degree가 0인 노드들을 queue에 삽입하면서 bfs를 통해서 순서를 출력한다~~
Author And Source
이 문제에 관하여(백준 2623 음악프로그램), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@josajang98/백준-2623-음악프로그램저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)