[Python] 백준 2623번: 음악프로그램

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

2623번: 음악프로그램

 

import sys
input = sys.stdin.readline


def solution():
    # input / set childs
    childs = [[] for _ in range(N+1)]

    for _ in range(M):
        curNums = list(map(int, input().split()))
        curLen = curNums[0]

        if curLen >= 2:
            for i in range(1, curLen):
                p, c = curNums[i], curNums[i+1]
                childs[p].append(c)

    # set entryLevels
    entryLevels = [0]*(N+1)
    for i in range(1, N+1):
        for c in childs[i]:
            entryLevels[c] += 1

    # initialize queue
    queue = []
    for i in range(1, N+1):
        if entryLevels[i] == 0:
            queue.append(i)

    # set toPrint
    toPrint = []
    while queue:
        cur = queue.pop(0)
        toPrint.append(cur)

        for c in childs[cur]:
            entryLevels[c] -= 1

            if entryLevels[c] == 0:
                queue.append(c)

    # print
    if len(toPrint) == N:
        for n in toPrint:
            print(n)
    else:
        print(0)


if __name__ == '__main__':
    N, M = map(int, input().split())

    solution()

 

위상정렬 알고리즘을 이용한다. https://www.acmicpc.net/problem/1005 ACM Craft와 매우 유사한 문제이다.

 

우선, childs라는 리스트에 입력받은 값을 적절히 넣을 것이다. childs[n]의 의미는, 노드 n의 자식들을 의미한다. 즉, childs[3] = [1,2,5]라고 하면, 3의 자식에 1, 2, 5가 있다는 것이다.

 

다음으로 childs를 통해 엔트리 레벨을 지정한다. 여기서, 엔트리 레벨이라고 함은, 해당 노드를 위해 필수적으로 수행해야하는 노드의 개수를 말한다. 즉, 부모의 개수이다.

예제 입력 1, 빨간색 글씨는 노드의 엔트리 레벨이다.

모든 노드에 대해 for문을 돌면서, 각 노드의 자식들에 대해, entryLevels[i] += 1을 해줌으로써 원하는 리스트를 만들 수 있다.

entryLevels가 왜 필요한지를 알기 위해서, 이후에 하게 될 탐색을 간략히 설명하겠다. 위 사진을 기준으로 설명하자면 아래 사진과 같다. 시작은, 엔트리 레벨이 0인 1과 6부터이다.

 

이것을 위해 우리는 queue가 필요하다. 엔트리 레벨이 0인 것들을 저장하여, 탐색하겠다는 의미의 큐이다. 엔트리 레벨이 0인 노드들부터 시작하므로, 이를 위해 큐를 초기화 시켜준다.

 

다음은 본격적인 탐색을 진행할 것이며, toPrint라는 리스트에 노드의 출력 순서를 담을 것이다.

우선 큐를 하나 꺼내서 이를 곧바로 toPrint에 담는다.

이후, 해당 노드의 자식들을 돌면서 엔트리 레벨을 감소시켜주는데, 감소시킨 결과 엔트리 레벨이 0이 되었다면 큐에 넣어준다.

 

마지막으로 toPrint를 돌면서 출력해주면 되는데, 만약 싸이클(순서를 정할 수 없는 경우를 의미한다.)이 생겼다면, entryLevels와 childs로 완벽히 탐색을 진행할 수 없으므로 toPrint의 길이가 N이 아니다. 따라서 N이 아닐 때는 0을 출력해준다.