[예제] [파이썬] [DP] 위상정렬(그래프 정렬)

위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘입니다.
각각의 일의 선후관계가 복잡하게 얽혀있을 때 각각 일의 선후관계를 유지하면서 전체 일의
순서를 짜는 알고리즘입니다.
만약 아래와 같은 일의 순서를 각각 지키면서 전체 일의 순서를 정한다면

 

1 4         //1번일을 하고 난 후 4번일을 해야한다.
5 4
4 3
2 5
2 3
6 2

 

 

전체 일의 순서는 1, 6, 2, 5, 4, 3과 같이 정할 수 있다. 전체 일의 순서는 여러 가지가 있습
니다 그 중에 하나입니다.

▣ 입력설명
첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어집니다.
두 번째 줄부터 M개의 정보가 주어집니다.

 

▣ 출력설명
전체 일의 순서를 출력합니다.

 

▣ 입력예제 1
6 6
1 4
5 4
4 3
2 5
2 3
6 2

 

▣ 출력예제 1
1 6 2 5 4 3

 

---

 

 

각 노드별 테이블을 만들고 '진입차수'를 기록한다.

4번 노드의 '차수'는 즉 연결개수, 간선의 개수는 3이고
'진입 차수'는 1에서 하나 5에서 하나, 총 2개이다

1부터 N까지 노드에 대해 기록할 1차원 배열을 만든다.
각 노드 idx에 진입차수를 기록한다

진입차수가 0이라는 의미는 가장 우선순위 바로 해도 되는 일이다.
큐를 만든다.
큐에서 빠진 값과 연결된 idx의 값을 감소시키며 반복한다.
0이되면 큐에 넣는다

 

 

---

import sys 
from collections import deque
sys.stdin=open('input.txt','r')

if __name__=="__main__":
    n,m=map(int, input().split())   # 일의 개수 n, 일의 순서 정보의 개수 m 
    graph=[[0]*(n+1) for _ in range(n+1)] 
    arr=[0]*(n+1)                   # 진입 차수 기록 
    Q=deque()
    
    for i in range(m):
        a,b=map(int, input().split())
        graph[a][b]=1
        arr[b]+=1               # 진입 차수를 카운트함 
    
    for i in range(1,n+1):
        if arr[i]==0:           # 진입 차수가 없을때 최우선순위가 됨, 즉, 다른 노드에서 들어오는게 없는 노드
            Q.append(i)         # Q에 넣는다
            
    # 이제 시작 
    while Q:
        x=Q.popleft()
        print(x, end=' ')
        for i in range(1,n+1):
            if graph[x][i]==1:      # x에 연결된 노드 찾기 연결되면 i의 진입차수 감소 시키기
                arr[i]-=1
                if arr[i]==0:       # 다시 또 진입차수가 0이 되면 
                    Q.append(i)     # 최우선순위가 되어 Q에 넣기

 

---

위 코드는 1부터 n까지 또 다 확인하는 방법이니깐 최종적으로 아래 코드가 정답이 되겠다.

import sys
from collections import  deque

sys.stdin=open('input.txt', 'r')

if __name__=="__main__":
    n,m=map(int, input().split())
    graph=[[] for _ in range(n+1)]
    arr=[0]*(n+1)
    Q=deque()
    
    for i in range(m):
        a,b=map(int, input().split())
        graph[a].append(b)
        arr[b]+=1
        
    for i in range(1, n+1):
        if arr[i]==0:
            Q.append(i)
    
    while Q:
        x=Q.popleft()
        print(x, end=' ')
        for i in graph[x]:
            arr[i]-=1
            if arr[i]==0:
                Q.append(i)