알고리즘 스터디 - 백준 2623번 : 음악프로그램

문제 해석

보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수의 순서를 정하는 프로그램

• [1, 4, 3], [6, 2, 5, 4], [2, 3] 각각 보조 PD들이 정한 순서인데 이를 만족하는 경우는 [6, 2, 1, 5, 4, 3]이나 [1, 6, 2, 5, 4, 3]이 존재한다.
• 남일이가 보조 PD의 순서를 만족하지 못하면 0을 출력

입력

1. N, M : 가수의 수, 보조 PD의 수
2. 보조 PD가 담당한 가수의 수가 나오고 보조 PD가 정한 순서들이 나옴

알고리즘 코드

from collections import deque

N, M = map(int, input().split())

degree = [0] * (N+1)
graph = [[] for _ in range(N+1)]

for _ in range(M):
    singer = list(map(int, input().split()))
    for i in range(1, singer[0]):
        graph[singer[i]].append(singer[i+1])
        degree[singer[i+1]] += 1

def topology_sort():
    result = []
    q = deque()
    # 초기에 진입차수 0인 노드들 큐에 넣기
    for i in range(1, N+1):
        if degree[i] == 0:
            q.append(i)

    # 큐가 빌때 까지 반복
    while q:
        node = q.popleft()
        # 꺼낸 원소는 위상 정렬 결과값에 append
        result.append(node)
        # 꺼낸 노드랑 연결된 노드들 탐색
        for next in graph[node]:
            degree[next] -= 1
            # 새롭게 진입차수가 0이 된 노드들 큐에 넣기
            if degree[next] == 0:
                q.append(next)
    return result

is_cycle = topology_sort()

if len(is_cycle) == N:
    for i in is_cycle:
        print(i)
else:
    print(0)

이번 문제는 순서를 정하려면 사이클이 없는 순서가 나와야 하고 어떤 특정 요소가 다른 요소보다 더 먼저 나와야 하는 위상 정렬알고리즘을 사용해야 한다. 그래서 입력 받은 요소를 graph에 들어갈 수 있게끔 바꿔주고 사용을 하게 되는데 이번 문제의 핵심은 위상 정렬이 되는지 안되는지 판별하는 것이다.

위상 정렬이 되지 않는 경우는 그래프의 사이클이 존재하는 경우인데 이를 확인하려고 찾아보니 2가지가 존재하고 있었다.

1) 진입차수에 0이 없는 경우
2) 위상 정렬을 한다음 노드의 개수가 일치하지 않는 경우이다.

이 때 1번을 사용했을 때는 틀렸는데 2번 요소로 했을 때 길이를 비교해보니 정답을 출력할 수 있었다. 이번 문제에서 내가 놓친 것은 이 문제가 어떤 유형인지 파악하는 것이고 잘한 것은 위상 정렬을 응용하여 풀었다는 것이다. 다음에는 더 발전해야겠다.