[Python Algorithm] Dynamic programming(동적계획법) - 위상정렬(그래프 정렬)

> Dynamic programming(동적계획법) - 위상정렬 : 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘, 그래프와 진입차수가 중요함 (두 가지를 만들어둬야 함)

예를 들어 아래의 그림을 보면 4번 정점의 진입차수는 1과 5에서 4로 향하는 방향 2개 존재. 그래서 진입차수는 2 이런 식으로 각각 차수 값을 저장해둬야함.

 

 

 

 

📖 문제 : 위상정렬(그래프 정렬)

 

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

 

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

 

 

 

코드

from collections import deque

if __name__ == "__main__":

    n, m = map(int, input().split())
    graph = [[0]*(n+1) for _ in range(n+1)]
    degree = [0]*(n+1)
    dQ = deque()
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a][b] = 1
        degree[b] += 1

    
    for i in range(1, n+1):
        if degree[i] == 0:
            dQ.append(i)

    while dQ:
        x = dQ.popleft()
        print(x, end=' ')
        for i in range(1, n+1):
            if graph[x][i] == 1:
                degree[i] -= 1
                if degree[i] == 0:
                    dQ.append(i)

 

 

Point ! ⭐️

• Queue를 만들어 진입차수가 0인 것을 넣는다. 0인 것들이 먼저 하는 작업이 되고, 0인 것을 수행한 후, 0인 것이 진입했던 다음 작업의 진입차수를 -1을 해주면서 0인 것을 또 찾으며 일의 순서를 정하면 되는 것
  예를 들어 아래의 그림으로 보면
  1)
  처음 작업 1과 작업 6이 진입 차수가 0이므로 Q=[1,6] 이 들어간다.
  Q에 있는 작업 1을 빼고(먼저 하는 작업이 됨) 작업 1이 향했던 작업 4의 진입차수 값을 -1을 해준다. 그럼 4의 진입차수는 2->1
  2)
  Q에 있는 작업 6을 빼면 작업 2의 진입차수는 1->0이 되어 작업 2가 Q로 들어가서 
  Q=[2] 가 되는 것.
  이 과정을 반복하면서 일의 순서를 정하면 됩니다.

 

 

 

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이