[백준/python]2623번 음악프로그램 - topology sort

문제 출처 - https://www.acmicpc.net/problem/2623

위상 정렬 문제 중 대표적인 문제다. 아마 다들 위상 정렬을 공부하고 풀었을텐데 나는 그냥 구현 느낌으로 코드를 작성했다. 주어지는 노드의 개수가 작기 때문에 쉽게 풀 수 있었던 것 같다.

1. 풀이

• 각 프로그램이 실행되기 위한 조건을 queue에 저장한다. 1 2 5 의 경우 G[2]에 1을 append, G[5]에 2를 append
• 모든 프로그램을 탐색하며 해당 번호의 큐의 길이가 0이면(전제 조건이 없는 경우) 방문 처리를 하고 answer배열에 순서대로 추가한다.
• 만약 현재 프로그램A의 전제 조건이 존재해서 queue에 다른 프로그램이 있는 경우 queue의 앞에서부터 pop을 하고 pop이 된 프로그램 B가 방문 처리가 되었다면 계속해서 pop한다.
• 프로그램 B가 방문 처리가 되지 않았다면 다시 queue에 append 하고 프로그램 A를 실행할 수 없으므로 반복문을 종료한다.
• 위와 같은 과정을 총 N번 반복했다. - 이 N번에 대한 근거는 그냥 벨만 포드 알고리즘과 유사한 방식으로 생각해서 풀었다. 반복문이 실행될 수록 queue의 길이가 짧아지기 때문에 가능한 풀이인 것인지 잘 모르겠다.

2. 코드

from collections import deque
N, M = map(int,input().split())
G = [ deque() for _ in range(N+1)]
for _ in range(M):
    order = list(map(int, input().split()))
    
    for i in range(2,len(order)):
        G[order[i]].append(order[i-1])
        
visited= [0 for _ in range(N+1)]
answer = []
for _ in range(N):
    for i in range(1,N+1):
        if visited[i]==0:
            if len(G[i])==0 : 
                visited[i]=1
                answer.append(i)
            else:
                while G[i] :
                    pre = G[i].popleft()
                    
                    if visited[pre]==0:
                        G[i].append(pre)
                        break
                    
                if len(G[i])==0 : 
                    visited[i]=1
                    answer.append(i)

if len(answer)==N:
    for i in range(N):
        print(answer[i])

else:
    print(0)

3. 위상정렬 코드

from collections import deque
N, M = map(int, input().split())
inDegree = [0 for _ in range(N+1)]
G=[ [] for _ in range(N+1) ]
G2 = [ []  for _ in range(N+1)]
for _ in range(M):
    order = list(map(int, input().split()))
    
    for i in range(2,len(order)):
        G[order[i]].append(order[i-1])
        G2[order[i-1]].append(order[i])
     
q= deque() 
for idx in range(1,N+1):
    inDegree[idx] = len(G[idx])
    if inDegree[idx]==0:
        q.append(idx)
         
answer = []        
while q:
    pre = q.popleft()
    answer.append(pre)
    for next in G2[pre]:
        inDegree[next]-=1
        
        if inDegree[next]==0:
            q.append(next)

if len(answer)!= N:
    print(0)
else:
    for i in range(N):
        print(answer[i])