[알고리즘] 위상정렬 알고리즘

위상 정렬이란, 사이클이 없는 방향 그래프의 모든 노드를 방향성을 거스르지 않도록(일의 선후관계 존재) 순서대로 나열하는 것을 말하는 정렬이다.

위상 정렬에선 진출 차수보다 진입 차수가 더 중요하다. 이 때, 진출 차수란 특정한 노드로부터 뻗어나가는 간선의 개수, 진입 차수란 특정 노드로 들어오는 간선의 개수를 말한다.

위상 정렬 알고리즘은 자료구조 큐와 진입 차수 개념을 활용한다.

📌문제

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

1 4 // 1번 일을 먼저 처리한 후 4번 일을 처리한다.
5 4
4 3
2 5
2 3
6 2

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

📌풀이

진입 차수를 나타내는 배열과 자료구조 큐, 그리고 그래프 연결 정보를 나타내는 배열을 준비한다.

이 때, 그래프의 연결 정보를 나타낼 때 선후관계를 나타낸 것이므로 양방향이 아닌 단방향 그래프임에 주의한다.

또한 입력 데이터를 예를 들었을 때, 1 4의 경우 1번을 처리한 후 4번을 처리한다는 의미이므로 4의 진입 차수는 1이 되는 것이므로 진입 차수를 나타내는 배열의 원소 4의 값을 1만큼 증가시킨다.

그렇게 위의 주어진 입력에 대한 정보를 진입 차수 배열에 나타내면 다음과 같다.

진입 차수 배열을 해석해보자면 0인 경우 먼저 해야하는 일이 없다는 의미로 먼저 처리할 수 있다는 것을 말한다. 따라서 값이 0인 것들을 먼저 자료구조 큐에 넣어준다.

import sys
input = sys.stdin.readline
from collections import deque

# N : 전체 일의 갯수
# M : 일의 순서 정보의 갯수
N, M = map(int, input().split())
# graph : 일의 선후관계를 나타낼 단방향 그래프
graph = [[0] * (N+1) for _ in range(N+1)]
# degree : 진입 차수를 나타내는 1차원 배열
degree = [0] * (N+1)
# 자료구조 큐
dQ = deque()

for i in range(M):
    # a번 작업 → b번 작업
    a, b = map(int, input().split())
    # a → b
    graph[a][b] = 1
    # b노드의 진입 차수 1만큼 증가
    degree[b] += 1

for i in range(1, N+1):
    # 진입 차수가 0이다? → 선행되는 작업이 없으므로 먼저 처리해도 무방한 작업들
    if degree[i] == 0:
        dQ.append(i)

while dQ:
    v = dQ.popleft()
    print(v, end=" ")
    # v라는 노드와 관계를 맺는 노드라면? → 진입 차수를 감소시킴
    for i in range(1, N+1):
        if graph[v][i] == 1:
            degree[i] -= 1
            # 진입 차수가 0이다? → 선행되는 작업이 없으므로 먼저 처리해도 무방한 작업들
            if degree[i] == 0:
                dQ.append(i)