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

백준 2623

보조 PD들이 가져온 모든 순서들을 만족하게 줄을 세우는 문제로 백준 2252번 문제와 유사하다. 주어진 입력을 어떻게 인접리스트와 진입 차수 배열로 나타낼 지만 해결한다면 동일한 방법으로 풀 수 있다.
문제에서 주어진 순서들이 사이클을 형성하지 않는다면 모든 순서를 정해 줄 수 있다. 하지만 반례로 보여준

[[1, 4, 3], [6, 2, 5, 4], [3, 2]]

로 순서가 주어진다면 어떤 노드를 먼저 방문해야 할 지 알 수 없다(4→3→2→5→4).
이런 상황이라면 진입 차수가 0이 되지 않고 아래 코드에서는 큐에 들어가지 않게 된다.

from collections import deque

N, M = map(int, input().split())
order = [list(map(int, input().split())) for _ in range(M)]
order = [od[1:] for od in order] # 보조 PD 번호는 필요 없음

graph = [[] for _ in range(N+1)] # 인접 리스트 초기화
in_order = [0 for _ in range(N+1)] # 진입 차수 배열 초기화
app = [] # 팀 순서

for od in order:
    for i in range(1, len(od)):
        graph[od[i-1]].append(od[i])
        in_order[od[i]] += 1

# 진입 차수가 0인 모든 노드를 큐에 추가
q = deque([i for i, val in enumerate(in_order[1:], 1) if val == 0])

while q:
    v = q.popleft() 
    app.append(v) # 진입 차수가 0이라면 팀 순서에 추가
    for next_v in graph[v]:
        in_order[next_v] -= 1
        if in_order[next_v] == 0:
            q.append(next_v)

if len(app) == N: # 모든 팀이 추가되었다면 출력
    print(*app, sep='\n')
else: # 팀이 부족하다면 0 출력
    print(0)