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

0.  문제 링크

 

 

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

2623번: 음악프로그램

---

1.  풀이 방법

 

 

1. 문제는 위상정렬로 해결하였다.
2. 다만 여기서는 중복이 발생할 수 있는데, 해결법은 두 가지로 나뉜다.
   1. set을 사용해서 후순위 노드를 하나만 집어넣고, degree도 1만 추가한다.
   2. list를 사용해서 후순위 노드를 (중복일지라도) 여러 개 집어넣고, degree도 여러 번 추가한다.
3. 2.2번 해결법을 사용하면, 속도는 느려진다.
4. 아무튼 최종적으로 만약 우선순위에 데드락이 걸리면, 0을 출력한다.

---

2.  코드

 

 

import sys
from collections import deque
input = sys.stdin.readline


if __name__ == "__main__":
    n, m = map(int, input().split())
    maps = [list(map(int, input().split())) for _ in range(m)]
    dq = deque()
    ans = []

    degree = [0] * (n + 1)
    sub_seq = [set() for _ in range(n + 1)]

    for seq in maps:
        for i in range(2, len(seq)):
            if seq[i] not in sub_seq[seq[i - 1]]:       # 중복처리
                degree[seq[i]] += 1     # 단계 추가
                sub_seq[seq[i - 1]].add(seq[i])     # 후순위 가수

    for i in range(1, n + 1):
        if degree[i] == 0:      # 제일 앞순위 가수
            dq.append(i)
    
    while dq:
        item = dq.popleft()
        ans.append(item)
        for i in sub_seq[item]:     # 후순위 가수들
            degree[i] -= 1
            if degree[i] == 0:      # 조건이 충족하면 덱에 넣음
                dq.append(i)    
            
    if len(ans) == n:   print(*ans, sep='\n')
    else:               print(0)

---

3.  마무리