[Algorithms] 동적 계획법(Dynamic Programming)-위상정렬(그래프 정렬)

 

1. 2차원 배열을 만들어서 예를들어 2->3으로 간다면 arr[2][3]=1 을 해줘서 선후 관계를 표현해준다

2. 1차원 배열을 만들어서 진입 차수 (들어오는 차수)의 개수를 입력한다. 예를 들어 2->3 으로 간다면 arr[3]+=1 을 해주고,      4->3 으로 간다면 arr[3]+=1 을 해줘서 arr[3]=2 가 된다 

3. 진입 차수가 0인 노드를 큐에 쌓아주고, pop 하면서 그 노드가 가리키는 노드의 진입차수를 -1 해주고

4. 노드의 진입차수를 -1 해줬는데 0의 값이 되었으면 더이상 그 노드를 가리키는 노드가 없으므로 큐에 쌓아준다

5. 큐 popleft 한 순서대로 print를 해준다 

 

if __name__=='__main__':
 
    n, m = map(int, input().split())
    graph = [[0]*(n+1) for _ in range(n+1)]     # 그래프 선후관계 표현을 위한 2차원 배열
    arr = [0] * (n+1)                           # 그래프 진입 차수의 기록을 위한 1차원 배열
    for i in range(m):
        start, end = map(int, input().split())
        graph[start][end] = 1                   # 그래프의 선후 관계를 입력을 받으며 기록한다
        arr[end] += 1
 
    queue = deque()
    for i in range(1, n+1):                     # 먼저 아무 진입 차수도 받지 못한 (0) 노드의 인덱스를
        if arr[i] == 0:                         # 큐에 쌓아준다
            queue.append(i)
 
    while queue:
        now = queue.popleft()                   # 큐를 pop을 해주면서
        print(now, end=' ')
        for i in range(1, n+1):
            if graph[now][i] == 1:              # 현재 노드가 가리키는 노드가 있다면
                arr[i] -= 1                     # 그 노드에 대한 진입차수를 일단 -1 해주고
                if arr[i] == 0:                 # 그 노드의 진입 차수가 0이 되버린 경우
                    queue.append(i)             # 큐에다 쌓아준다