위상정렬(그래프)

[hello2jolee]

• 연결 이슈 : https://github.com/hello2jolee/algorithm_python/issues/13

위상정렬(그래프 정렬)

• 어떤 일을 하는 순서를 찾는 알고리즘
• 각각의 일의 선후관계가 복잡하게 얽혀있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘

진입차수란?

• 나에게 인입되는 화살표의 수

  1 4 # 1번 일을 하고 난 후 4번 일을 해야한다.
  5 4
  4 3
  2 5
  2 3
  6 2
  
  # degree[1] = 0, degree[2] = 1, degree[3] = 2, 
  # degree[4] = 2, degree[5] = 1, degree[6] = 0

[hello2jolee]

from collections import deque

def solution(N, M, array):
    # 데이터 저장용 그래프
    graph = [[0] * (N + 1) for _ in range(N + 1)]
    # 진입차수 계산용도
    degree = [0] * (N + 1)
    dQ = deque()

    for a, b in array:
        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)