[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 13

위상정렬(그래프 정렬)

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

import sys
sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline
from collections import deque

n,m = map(int, input().split())
g = [[0] * (n+1) for _ in range(n+1)]
degree = [0] * (n+1) #진입차수
dq = deque()

for i in range(m): #간선
    a,b = map(int, input().split()) #방향 그래프 !!!
    g[a][b] = 1
    degree[b] += 1 #진입차수 a->b니까 b값을 올려야지

for i in range(1,n+1):
    if degree[i] == 0: #진입차수가 0이면
        dq.append(i) #진입차수가 0이라는 것은 선행해야 하는 작업이 없다는 것이다.

while dq:
    x = dq.popleft()
    print(x, end = " ") #여기서 출력한다는 것은 x 작업을 했다는 뜻 !
    #x의 작업을 했으니 이제 진입차수를 제거해줘야해
    for i in range(1,n+1):
        if g[x][i] == 1: #만약 x에서 흐르다면...
            degree[i] -= 1
            if degree[i] == 0:
                dq.append(i)

😀 코멘트

위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘이라고 생각하자. 그렇게 생각하면 문제풀기 쉬워진다.