[Python] 2623 - 음악 프로그램 (골드3)

1. 문제 설명

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

2623번: 음악프로그램

 

---

2. 아이디어

[Python] 1516 - 게임개발 (골드3)

이전에 다룬 위상 정렬 문제를 풀어보면 이것도 같은 문제라는 걸 알 수 있다.

 

테스트 케이스의 정점 연결 정보와 위상 차원 수를 저장해두면 다음과 같다

 

설명하자면 정점 1번의 자식노드는 4고, 위상차원 수는 1개임을 의미한다.

여기서 위상차원 수가 0인, 즉 선행 조건이 존재하지 않는 정점 1, 6은 서로의 순서 상관없이 가장 앞으로 오면 된다.

대신 리스트에 추가하기 전에 자신의 자식 노드의 위상 차원을 1씩 내려주다가

0이 되면 자식노드를 큐에 넣어주고 퇴장하면 되는 문제다.

 

---

3. 코드

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    indegree = [0] * (n+1)
    result = []

    for i in range(m):
        _input = list(map(int, input().split())) # _input[0] : 정점, 그 외에는 모두 이동 가능한 곳
        for j in range(1, _input[0]):
            graph[_input[j]].append(_input[j+1])
            indegree[_input[j+1]] += 1 # 정점을 기준으로 이동할 곳에 진입 차수 1증가

    queue = deque()

    for i in range(1, n+1):    
        if indegree[i] == 0:
            queue.append(i)
        
    while queue:
        tmp = queue.popleft()
        result.append(tmp)
        for i in graph[tmp]:
            indegree[i] -= 1
            if indegree[i] == 0:
                queue.append(i)
    
    if len(result) != n:
        print(0)
        return

    for i in result:
        print(i)

solution()