문제

[백준] 음악프로그램 (Gold 3)

요약

  • M명의 보조 PD들이 N명의 가수들 중 자신이 담당한 가수들의 출연 순서를 정한다.
  • 한 명의 가수를 여러 명의 보조 PD가 담당할 수 있다.
  • 보조 PD들이 정한 순서를 모두 존중하며 모든 가수들의 출연 순서를 정하자.
  • 만약 순서를 정하는 것이 불가능하다면 0을 출력한다.
  • 답이 여럿일 경우 아무거나 하나를 출력한다.

분류

  • 위상 정렬

풀이

1. 내 풀이 (위상 정렬)

  • 전형적인 위상정렬 문제이다.
  • 불가능한 경우는 사이클이 생기는 경우이다. 만약 위상 정렬 알고리즘을 수행하는 방향 그래프에 사이클이 존재한다면, 큐에 아무 노드도 push 되지 않아 알고리즘이 종료되지만 여전히 진입 차수가 1인 노드가 존재한다.


import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
cnts = [0] * n

for _ in range(m):
    arr = list(map(int, input().split()))[1:]

    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            graph[arr[i] - 1].append(arr[j] - 1)
            cnts[arr[j] - 1] += 1

queue = deque([i for i in range(n) if cnts[i] == 0])

ans = []
while queue:
    cur = queue.popleft()
    ans.append(cur + 1)
    for i in graph[cur]:
        cnts[i] -= 1
        if cnts[i] == 0:
            queue.append(i)

if sum(cnts) == 0:
    for a in ans:
        print(a)
else:
    print(0)