백준 - [Gold 2] 2623번 음악프로그램

문제링크: https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

---

문제 설명

- N: 가수의 수

- M: 보조 PD의 수

- 각 보조 PD가 정한 가수의 순서가 주어질 때 모든 보조 PD의 순서를 만족하는 가수의 순서를 출력

- 답이 여러개일 경우 아무거나 출력, 답이 없을경우 0 출력

- ex) 보조PD가 3명(M)일 때 입력이 아래와 같이 주어지면

• 1 4 3
• 6 2 5 4
• 2 3

=>  6 2 1 5 4 3 or 1 6 2 5 4 3 이 정답이 된다.

---

풀이

위상정렬 문제였습니다.

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
말이 어려운데, 선수과목을 생각하면 된다. 선수과목을 들어야 다음과목을 들을 수 있는 것처럼 순서가 주어지면 그에 따라 정렬해야 하는 것입니다.
출처: https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

 

위상정렬을 풀 때는 indegree(진입차수)와 path(다음 방문)을 관리해주어야 합니다. (코드에서 확인)

이 문제 같은경우는 기본 위상정렬 문제에서 두가지 차이점이 있습니다.

1. 답이 없을 경우 0출력: 마지막에 정답 개수를 체크하는 식으로 해결

2. 각기 다른 순서의 조건을 가지고 있음: 하나의 indegree와 path로 관리함으로써 해결

 

코드

from sys import stdin
from collections import defaultdict
from collections import deque

stdin = open("input.txt", "r")

# N: 가수의 수
# M: 보조 PD의 수
N, M = map(int, stdin.readline().split())

ind = [0 for _ in range(N+1)] # 진입 차수
path = defaultdict(lambda: []) # 다음 방문

# 입력 받으며 진입 차수와 다음 방문 업데이트
for _ in range(M):
    singers = list(map(int, stdin.readline().split()))[1:] # 0 번째는 숫자이므로
    for i in range(len(singers) - 1): 
        path[singers[i]].append(singers[i+1])
        ind[singers[i+1]] += 1

# 진입 차수가 0인 지점들 먼저 넣기        
queue = deque()
for i in range(1, N+1):
    if ind[i] == 0: queue.append(i)

# 위상 정렬
# queue를 이용해 pop하며 다음 방문의 진입차수를 줄이며 업데이트
answer = []
while queue:
    s = queue.popleft()
    answer.append(s)

    # 진입 차수 업데이트
    for i in path[s]:
        ind[i] -= 1
        if ind[i] == 0:
            queue.append(i)

# 못 갈 경우
if len(answer) != N:
    print(0)
else:
    for _ in answer:
        print(_)