태그를 보니 위상 정렬에 관한 문제는 하나 뿐이라서 위상 정렬에 관한 문제 풀이를 적어보려고 한다.

BOJ 2623 - 음악프로그램 링크
(2022.10.25 기준 G3)
(치팅 NO)

문제

N명의 가수가 있고 M명의 PD가 각 가수들의 출연 순서를 정했을 때
출연 순서들을 지키면서 전체 가수의 순서를 정하기

알고리즘

방향 그래프의 순서를 정하는 것은 위상 정렬
단, 위상 정렬이 가능한 방향 그래프인지 확인해야 한다.

풀이

문제 지문을 보면 세번째 보조 PD가 3 2로 정해왔으면 전체 순서를 정하는 것이 불가능하다고 되어 있다.
만약 3 2로 정해왔을 때를 그래프로 나타내어 보면

(4 -> 3 -> 2 -> 5 -> 4) 순환이 생기는 것이 보인다.
만약 이 상태에서 위상 정렬을 하게 되면, 1과 6이 정렬된 결과에 담겨도 1과 6과 연결된 4와 2는 진입차수 2에서 1로 감소하므로 덱에 담기지 않아 그대로 위상 정렬이 종료된다.

결국은 DAG(비순환 방향 그래프)가 아닌 방향 그래프에서 위상 정렬을 하게 되면 정렬 결과에 모든 원소가 온전히 담기지 못한다. 이와 같은 이유로 위상 정렬은 사이클이 없는 방향 그래프에서만 가능하다는 것이다.

코드

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

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)] # 순서
ind = [0] * (N + 1) # 진입차수

# 그래프 및 진입차수 채우기
for _ in range(M):
    n, *singers = map(int, input().split())
    for i in range(n - 1):
        graph[singers[i]].append(singers[i + 1])
        ind[singers[i + 1]] += 1

# 진입차수가 0인 가수를 덱에 넣기
queue = deque()
for i in range(1, N + 1):
    if not ind[i]:
        queue.append(i)

# 위상정렬 순서를 result에 담기
result = []
while queue:
    i = queue.popleft()
    result.append(i)
    for j in graph[i]:
        ind[j] -= 1
        if not ind[j]:
            queue.append(j)

# 만약 그래프가 DAG가 아니라면 result에는 모든 가수가 나타나지 않는다.
print(*result, sep = '\n') if len(result) == N else print(0)

여담

KOI 2002 중등부 문제 중 하나인데, 생각해보면 코딩이 지금처럼 인기가 없는 2002년 중학생 때 이 문제를 접했다고..? 진짜 대단한 사람들이다.