[백준 2623번] 음악 프로그램 - python / 위상 정렬

문제 링크

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

풀이 

- 어렵다............어우 헷갈려 

위상 정렬 알고리즘 사용해서 풀이 

: 방향 그래프의 모든 노드를 방향성에 거르지 않도록 순서대로 나열하는 것 

 

위상 정렬 알고리즘으로 순서대로 나열했을 때 모든 가수가 등장하지 않으면 순서를 정할 수 없는 것 

from collections import deque

# 위상 정렬 알고리즘 
def topology_sort():
    result = []
    q = deque()
    
    # 진입 차수 0인 것 큐에 삽입 
    for i in range(1,n+1):
        if indegree[i] == 0:
            q.append(i)
            
    while q :
        now = q.popleft()
        result.append(now)
        
        for i in graph[now]:
        	# 진입 차수 줄이기 
            indegree[i] -= 1 
            
            if indegree[i] == 0 :
                q.append(i)

	# 모든 가수의 순서를 정할 수 없으면 
    if len(result) != n:
        print(0)
    else:
        for i in result:
            print(i)
    
n, m = map(int,input().split())

# 진입 차수 
indegree = [0] * (n+1)
graph = [ [] for _ in range(n+1) ] 

for _ in range(m):
    seq = list(map(int,input().split()))
    for i in range(1, len(seq)-1):
    	# seq[i]에서 seq[i+1] 로 이동 
        graph[seq[i]].append(seq[i+1])
        indegree[seq[i+1]] += 1 
        
topology_sort()