Part7.14_동적프로그래밍(DynamicProgramming)_위상정렬(그래프 정렬)

문제

위상 정렬이란


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

입력

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

출력

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

정답 풀이

• 1. 방향그래프인 이차원 리스트에 값을 초기화 한다.
     
• 2. 차수를 확인하면서 "진입 차수"를 일차원 리스트에 누적한다.
     
• 3. deque를 활용한다. 진입차수가 없는, 즉 먼저 일을 실행해도 상관 없는 노드를 deque에 append 시킨다.
     
     작업한 간선의 수는 1을 줄여준다.

• 4. deque가 비워질 때 까지 반복한다.
     

정답 코드

import sys
sys.stdin = open ("input.txt", "rt")
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    #n은 일의 개수 m은 정보의 개수
    n,m = map(int,input().split())
    graph = [[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())
        graph[a][b] = 1 #a 작업하고 b 작업하는 방향 그래프(즉 a에서 b로만 흐를 수 있다는 의미이다.)
        degree[b] += 1 #b로 진입하므로 진입차수 누적
    for i in range(1, n+1):
        if degree[i]==0: #차수가 0이면, 즉 선행될 작업이 없다면
            dQ.append(i) # dQ애 추가한다.
    while dQ:
        x=dQ.popleft()
        print(x,end=' ')
        for i in range(1, n+1):
            if graph[x][i]==1: #pop한 작업의 진입차수를 대상을 찾아 -1한다.(작업실행)
                degree[i] -= 1
                if degree[i]==0: #더 이상 할 일이 없다면 append 시킨다.
                    dQ.append(i)