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

[Gold III]

 

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

2623번: 음악프로그램

 

풀이

보자마자 위상 정렬부터 생각이 났다.

근데 문제에서 사이클이 있을 수 있다는 것을 명시함. (위상 정렬은 사이클이 없을 때 적용 가능.)

 

처음에는 Union-Find를 이용해 미리 사이클이 있는 지를 검증하고 해야하나 생각했으나,

굳이 그러지 않아도 진행 과정에서 사이클이 존재한다면, N개를 모두 돌지 못하고 종료되므로 예외처리에 넣어줌.

from collections import deque
N, M = map(int, input().split())
 
graph_in_cnt = dict(zip([i for i in range(1, N+1)], [0 for _ in range(N)]))
graph_in = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))
graph_out = dict(zip([i for i in range(1, N+1)], [[] for _ in range(N)]))
 
for _ in range(M):
    a = list(map(int, input().split()))
    k = a[0]
    for i in range(1, k):
        graph_in_cnt[a[i+1]] += 1
        graph_in[a[i+1]].append(a[i])
        graph_out[a[i]].append(a[i+1])
 
queue = deque()
for i in graph_in_cnt:
    if graph_in_cnt[i] == 0:
        queue.append(i)
 
result = []
while queue:
    a = queue.popleft()
 
    for g in graph_out[a]:
        graph_in_cnt[g] -= 1
        if graph_in_cnt[g] == 0:
            queue.append(g)
 
    result.append(a)
 
# result에 N개의 원소가 없다면, 사이클이 생겨 온전하게 종료되지 못한 것.
if len(result) == N:
    for i in result:
        print(i)
else:
    print(0)