[백준] 2623번 음악 프로그램 / 위상 정렬 알고리즘

 

위상 정렬을 모르면 정말 풀기 힘든 문제이다. 유튜브 강의를 듣고 공부하고 참고해서 코드를 작성했다. 파이썬 코딩테스트 2주차, 처음 위상 정렬을 접해보니 정말 어려웠다. 요 개념은 따로 포스팅을 자세하게 하면서 공부해봐야겠다! 

 

나의 코드 : 

from collections import deque
node,count = map(int, input().split())

connected = [0]*(node+1)
graph = [[] for _ in range(node+1)]
#connected = 모든 노드에 대한 진입차수 0으로 초기화
#graph = 각 노드에 연결된 간선 정보를 담은 연결 리스트 초기화


#방향 그래프의 모든 간선 정보 입력 받기 
for _ in range(count):
    A = list(map(int,input().split()))
    N = A[0]
    L = A[1:]
    for i in range(1,N):
        graph[L[i-1]].append(L[i])
        connected[L[i]] += 1

# connected = 각 인덱스에 진입차수 몇개인지 표현
# graph = 각 인덱스에 몇개의 노드가 연결되어 있는지 표현 

def Fn():
    answer = [];
    q = deque()
    
    for i in range(1, node+1):
        if connected[i]==0:
            q.append(i)
    
    if len(q) <=0: print(0)
    while q:
        ele = q.popleft()
        answer.append(ele)
        for i in graph[ele]:
            connected[i] -= 1
            if connected[i] ==0:
                q.append(i)
        if len(answer)==node:
            for n in answer:
                print(n)
            break
    else:
        print(0)
             
Fn()

 

 

 

Reference : 한빛미디어 https://www.youtube.com/watch?v=xeSz3pROPS8