음악프로그램 ( 2623 번 )

2623번: 음악프로그램

 

🧠 알고리즘

- 각 PD의 정보를 종합해 자식, 부모 정보 딕셔너리에 저장
- 위상 정렬을 수행.. ( 부모가 없으면 큐 삽입 )
- 최종, 모든 노드 방문 못하면 0.. 모든 노드 방문 시 줄 세운 결과 출력!!

 

🧾 코드

from collections import deque
import sys

def _mk(n, m):
    a1, a2 = {}, {}
    
    for i in range(1, n + 1):
        a1[i], a2[i] = [], 0

    for _ in range(m):
        n_list = list(map(int, sys.stdin.readline().rstrip().split()))
        for idx in range(1, len(n_list) - 1):
            p, c = n_list[idx], n_list[idx + 1]
            a1[p].append(c)
            a2[c] += 1
        
    return a1, a2


def _main(ch, pt, num):
    answer = []
    queue = deque([k for k, v in pt.items() if v == 0])

    while queue:
        now_q = queue.popleft()
        answer.append(now_q) # 줄 세우기

        for c in ch[now_q]:
            pt[c] -= 1
            if pt[c] == 0: # 더 이상 루트가 없는 경우..
                queue.append(c)

    if len(answer) != num: # 순서 정하는 것이 불가능..
        return 0
        
    return '\n'.join(map(str, answer))


n, m = map(int, sys.stdin.readline().rstrip().split())
ch, pt = _mk(n, m)
print(_main(ch, pt, n))

 

⏱️ 시간 복잡도

_mk() : 부모, 자식 종합 정보 구하는 함수 ( 이차형 시간 복잡도 )
_main() : 위상정렬 줄 세우기.. ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )