Algorithm - 위상정렬(그래프 정렬)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[위상정렬(그래프 정렬)]

 

위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘이다.

각각의 일의 선후관계가 복잡하게 얽혀있을 때, 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘이다.

 

만약, 아래와 같은 일의 순서를 지키면서 전체 일의 순서를 정한다면 전체 일의 순서는 1, 6, 2, 5, 4, 3과 같이 정할 수 있다. 전체 일의 순서는 여러 가지가 있으며 위의 예시는 그 중 하나이다.

 

예시

 

 

*입력 설명

첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어진다.

두 번째 줄부터 M개의 정보가 주어진다.

 

*출력 설명

전체 일의 순서를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
from collections import deque
sys.stdin = open('AA/input_85.txt', 'rt')

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
    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)
                
# 출력 : 1 6 2 5 4 3

 

input_85.txt(입력)

6 6
1 4
5 4
4 3
2 5
2 3
6 2

 

 

중요내용

1. 해당 문제는 자료구조 Queue를 활용한다.
2. 진입 차수는 특정 노드에 들어오는 간선을 뜻한다.
3. 리스트 degree에는 각 노드의 진입차수(해당 노드로 들어오는 간선)의 개수를 저장한다.
4. 2차원 리스트 graph는 인접행렬로 방향 그래프를 표현하기 위해 사용된다.
5. graph[a][b] = 1은 무조건 a에서 b방향으로만 이동할 수 있음을 의미한다.
6. 위의 코드에서 1은 a노드에서 b노드로 이어져 있는 간선의 개수를 뜻한다.
7. graph[a][b] = 1의 코드처럼 a노드에서 b노드로 진입차수가 존재하면 이를 degree 리스트에 저장해줘야 한다.
8. 즉, degree[b] = 1의 코드를 통해 b노드로 들어오는 진입차수의 개수를 저장한다.
9. 만약, 특정 노드의 진입차수가 0이라면 이는 해당 작업을 수행하기 전에 미리 수행되어야 할 작업이 존재하지 않음을 의미한다.
10. 따라서, 진입차수가 0인 작업들은 자료구조 Queue에 넣어서 해당 작업을 실행할 준비를 한다.
11. 자료구조 Queue에 들어간 작업들이 popleft() 함수를 통해 Queue 밖으로 나오면 이는 해당 작업이 실행된 것을 의미한다.
12. 특정 작업을 실행하고 난 후에는 반드시 리스트 degree에서 진입차수의 개수를 1개 줄여줘야 한다.