알고리즘 / 자료구조’ 시리즈

[이.취.코] 위상 정렬 (Topology Sort)

  • 0
  • 0
0
0

1. 위상 정렬

방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.

정렬 알고리즘의 일종이다. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.

그래프상에서 선후관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.

A. 진입차수 (Indegree)

특정한 노드로 들어오는 간선의 개수

주어진 방향 그래프에서 위상 정렬을 수행하는 구체적인 알고리즘

  1. 진입차수가 0인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 다음의 과정을 반복한다.
    1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

큐가 빌 때까지 큐에서 원소를 계속 꺼내서 처리하는 과정을 반복한다. 이떄 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하낟고 판단할 수 있다. 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다. 사이클이 존재하는 경우 사이클에 포함되어 있는 원소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문이다.

기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많다.

B. 위상 정렬

a. 예시
  • step 0

    진입차수가 0인 노드를 큐에 넣는다.

    노드1234567
    진입차수0112121
    노드 1
  • step 1

    큐에 들어 있는 노드 1을 꺼낸다. 노드 1과 연결되어 있는 간선들을 제거한다. 노드 2와 노드 5의 진입차수가 0이 된다. 노드 2와 노드 5를 큐에 삽입한다.

    노드1234567
    진입차수0012021
    노드 2노드 5
  • step 2

    큐에 들어 있는 노드 2를 꺼낸다. 노드 2와 연결되어 있는 간선들을 제거한다. 노드 3의 진입차수가 0이 된다. 노드 3을 큐에 삽입한다.

    노드1234567
    진입차수0002011
    노드 5노드 3
  • step 3

    큐에 들어 있는 노드 5를 꺼낸다. 노드 5와 연결되어 있는 간선들을 제거한다. 노드 6의 진입차수가 0이 된다. 노드 6을 큐에 삽입한다.

    노드1234567
    진입차수0002001
    노드 3노드 6
  • step 4

    노드 3을 꺼낸다. 노드 3과 연결되어 있는 간선들을 제거한다. 새롭게 진입차수가 0이 되는 노드가 없으므로 그냥 넘어간다

    노드1234567
    진입차수0001001
    노드 6
  • step 5

    노드 6을 꺼낸다. 노드 6과 연결되어 있는 간선을 제거한다. 노드 4의 진입차수가 0이 된다. 노드 4를 큐에 삽입한다.

    노드1234567
    진입차수0000001
    노드 4
  • step 6

    노드 4을 꺼낸다. 노드 4과 연결되어 있는 간선을 제거한다. 노드 7의 진입차수가 0이 된다. 노드 7을 큐에 삽입한다.

    노드1234567
    진입차수0000000
    노드 7
  • step 6

    노드 7을 꺼낸다. 노드 7과 연결되어 있는 간선을 제거한다. 새롭게 진입차수가 0이 되는 노드가 없으므로 그냥 넘어간다.

    노드1234567
    진입차수0000000
b. 결론

큐에서 빠져나간 노드를 순서대로 출력하면, 위상 정렬을 수행한 결과가 된다. 위상 정렬의 답안은 여러 가지가 될 수 있다는 점이 특징이다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면, 여러 가지의 답이 존재하게 된다.

위 예시에서는 1 - 2 - 5 - 3 - 6 - 4 - 7 또는 1 - 5 - 2 - 3 - 6 - 4 - 7이 될 수 있다.

c. 소스코드

from collections import deque  
  
v, e = map(int, input().split())  
indegree = [0] * (v+1)  
graph = [[] for i in range(v+1)]  
  
for _ in range(e):  
    a, b = map(int, input().split())  
    graph[a].append(b)  
    indegree[b] += 1  
  
def topology_sort():  
    result = []  
    q = deque()  
  
    for i in range(1, v+1):  
        if indegree[i] == 0:  
            q.append(i)  
  
    while q:  
        now = q.popleft()  
        result.append(now)  
  
        for i in graph[now]:  
            indegree[i] -= 1  
  
            if indegree[i] == 0:  
                q.append(i)  
  
    for i in result:  
        print(i, end=' ')  
  
topology_sort()

d. 시간 복잡도

시간 복잡도는 O(V+E)이다. 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해야 한다. 노드와 간선을 모두 확인한다는 측면에서 O(V+E)의 시간이 소요되는 것이다.

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.