백준 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를 통해서 순서를 출력한다~~