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

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

 

#백준 2623 음악프로그램
import sys
from collections import deque
input = sys.stdin.readline

# N: 가수 수, M: 보조 PD의 순서 정보 개수
N, M = map(int, input().split())

# orders[a] : a 가수 다음에 나와야 하는 가수들의 리스트
orders = [[] for _ in range(N+1)]

# in_degree[i] : i번 가수의 진입 차수(앞에 와야 하는 가수 수)
in_degree = [0 for _ in range(N+1)]

# M개의 순서 정보 입력
for _ in range(M):
    order = list(map(int, input().split()))
    order_num = order.pop(0)  # 이 줄은 실제로 안 써도 됨 (선행 가수 개수)
    
    # 순서대로 간선 생성
    for i in range(len(order) - 1):
        prev = order[i]
        next = order[i+1]
        orders[prev].append(next)  # prev → next
        in_degree[next] += 1       # next의 진입 차수 증가

# 위상정렬을 위한 큐
q = deque()

# 진입 차수가 0인 가수(앞에 아무도 없는 가수)를 큐에 추가
for i in range(1, N+1):
    if in_degree[i] == 0:
        q.append(i)

ans = []

# 위상정렬(Kahn’s algorithm)
while q:
    curr = q.popleft()
    ans.append(curr)  # 현재 가수 순서 확정

    # 현재 가수 뒤에 와야 하는 가수들의 진입 차수 감소
    for next in orders[curr]:
        in_degree[next] -= 1
        if in_degree[next] == 0:
            q.append(next)

# 사이클 여부 체크
# 모든 가수를 다 순서에 포함하지 못했다면 사이클 존재 → 0 출력
if len(ans) != N:
    print(0)
else:
    for val in ans:
        print(val)

BFS 위상정렬인 Kahn 알고리즘을 이용하여 해결하였다.

사이클이 있는 경우 전체 크기가 N이 되지 않는다. 이 점을 이용하여 사이클 판별이 가능하다.