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

개요

위상 정렬은 DAG에서 정점의 순서를 정하는 데 사용하는 알고리즘입니다. 이는 대학교 선수 과목으로 쉽게 비유를 할 수 있습니다. 일부 과목들은 앞의 몇 개의 선수과목을 이수해야 들을 수 있는 경우가 있는데, 이런 경우까지 전부 체크해서 1학년 부터 4학년 까지 들어야 하는 과목의 순서를 나열할 때, 이 알고리즘을 사용하면 해결이 가능합니다.

원리

위상 정렬의 원리는 부모 정점과 이어저 있는 간선의 갯수(차수)를 파악하는 것입니다. 어떤 정점에서 몇 개의 차수가 있다는 것은 해당 정점을 탐색하기 전에 몇 개의 다른 정점을 탐색해야 해당 정점을 탐색할 수 있다는 의미가 됩니다.
즉 만약에 어떤 정점을 탐색을 완료했다면, 해당 정점의 탐색을 완료했기 때문의 해당 정점과 연결되어 있는 다음 정점들은 해당 정점과의 간선을 끊게 됩니다. 이로 인해 다음 정점들의 차수들은 1씩 줄어들게 되고, 이 중 차수가 0인 정점들은 최우선 탐색 대상이 되므로 큐에 추가하고 그 다음 반복문에 바로 탐색해서 리스트에 추가하게 됩니다. 이 순서를 큐에 더이상 데이터가 남아있지 않을 때 까지 반복하게 됩니다.

위상 정렬은 사이클도 판단할 수 있다.

사이클을 판단하는 방법은 위상 정렬을 수행하고 난 뒤에 정렬된 정점의 갯수가 기존의 정점이 갯수와 일치하는지 판단을 하는 방법인데, 이때 정렬된 정점의 갯수가 기존의 정점 갯수보다 더 적으면 사이클로 판단합니다.
예를 들어 1 -> 2 -> 3 -> 4 -> 2 로 이어지는 DAG가 있다고 가정합시다. 1의 차수는 0이므로 1에서 부터 시작하고 2로 넘어가야 하는데, [1 -> 2] 사이에서의 간선을 잘라 2의 차수를 1로 줄여도 [4 -> 2]가 있기 때문에 차수가 1이 되어 큐에 추가하지 못하고 반복문을 종료하게 됩니다. 이때 결과는 [1]이 되고 요소 갯수가 1이 되므로 실제 정점 갯수(4개)보다 더 적게 됩니다. 이렇게 해서 DAG상에서의 사이클 여부를 검수할 수 있습니다.

위상 정렬의 시간 복잡도는 O(V+E)

V가 정점의 갯수, E가 간선의 갯수라고 할 때, 위상 정렬의 시간복잡도는 O(V+E)가 됩니다. 모든 정점의 차수가 0이 될 때 까지 모든 간선을 탐색하고(E), 차수가 0이 되어야 정점에 접근할 수 있기 때문에 모든 정점은 한 번 씩만 접근하기 때문입니다.(E+V)

위상 정렬은 성향에 따라 결과가 달라질 수 있다.

마지막으로 위상 정렬은 완벽하게 구현해도 사람에 따라 정렬 결과가 달라질 수 있습니다. 예를 들어서 정점을 담을 때 큐를 사용할 수도 있고, 스택도 사용할 수 있는데 이때 정렬 결과는 달라집니다.
하지만 어디까지나 같은 깊이에서만 정렬 순서가 다르기 때문에 이는 크게 문제가 되지 않습니다. 실제로 위상 정렬을 이용해 순서를 정하는 알고리즘 문제의 일부분은 알고리즘의 결과가 예제와 달라도 크게 차이가 없으면 정답처리 되는 경우도 있습니다.
예를 들어 1 -> (2, 3) -> 4 가 있다고 가정할 때, 위상 정렬 적용 후의 순서는 [1 -> 2 -> 3 -> 4] 또는 [1 -> 3 -> 2 -> 4] 이렇게 두 가지가 될 수 있는데, 전부 맞는 순서 입니다.
그래도 순서를 꼭 일치시키고자 할 때, 같은 깊이의 정점들 사이에서도 우선순위를 정하면 됩니다. 그 방법으로 큐를 우선순위 큐(또는 힙)으로 바꾸는 방법이 있습니다.
예를 들어 아까 위의 예제에서 정점의 값이 작은 순서대로 정렬을 하고싶다고 하면, 파이썬의 경우 heapq 모듈을 이용해 최소 힙을 활용하여 [1 -> 2 -> 3 -> 4]라는 고정된 순서를 출력할 수 있습니다.

코드 보기(Python)

import collections

def topological_sort(graph, n):
    """
    :param graph: 그래프
    :param n: 노드 갯수
    """
    answer = []
    parent_size = collections.defaultdict(int)
    # 해당 정점에서 부모 정점 갯수(차수) 구하기
    for _, childs in graph.items():
        for child in childs:
            parent_size[child] += 1

    # 차수가 0인 정점(최우선순위) 찾아서 큐에 추가
    # 동일한 깊이에서의 우선순위까지 고려할 경우 heapq모듈을 활용
    """
    import heapq

    queue = []
    # push
    heapq.heappush(queue, v)
    # pop
    v = heapq.heappop(queue)
    """
    queue = collections.deque()
    for start in range(1, n+1):
        if parent_size[start] == 0:
            queue.appendleft(start)

    while queue:
        # 큐에 있는 정점은 최우선순위에 있는(실행 가능한) 정점이다.
        # 따라서 순서 리스트에 추가한다.
        u = queue.pop()
        answer.append(u)

        for v in graph[u]:
            # 다음으로 넘어갈 정점들
            # 현재 정점이 실행됐으므로 다음 정점의 차수를 1 감소시킨다.
            parent_size[v] -= 1
            if parent_size[v] == 0:
                # 부모 차수가 0인 정점 -> 최우선순위
                queue.appendleft(v)
    
    if len(answer) < n:
        # 사이클 판단.
        # 정렬된 노드의 수가 실제 노드 갯수보다 작으면 사이클이 존재한다
        # 그 이유는 사이클이 존재할 경우, 다음 노드에 더 이상 접근할 수 없기 때문이다.
        return None
    return answer

n = 5
"""
그래프
    1-->2
    !   !
    `-->3->-.
        !   !
        4-->5
결과 1 -> 2 -> 3 -> 4 -> 5
"""
graph = {
    1: [2, 3],
    2: [3],
    3: [4, 5],
    4: [5],
    5: []
}

result = topological_sort(graph, n)

if not result:
    # 사이클
    print("사이클이 감지되었습니다.")
else:
    print(*result)

 

 

풀어볼 만한 문제들

풀어볼 만한 문제라기보다는 그냥 제가 풀었던 위상정렬 문제들만 나열할 뿐입니다. 마지막 하나 빼구요

2252번: 줄 세우기

위상 정렬의 기본 문제 입니다. 정렬 일부가 달라도 우선순위가 맞다면 통과됩니다.

1766번: 문제집

기본 위상 정렬에 우선순위라는 조건이 붙어 있습니다.

2623번: 음악프로그램

위상 정렬문제에 사이클 여부를 판단하는 조건이 생겼습니다.

1005번: ACM Craft

위상 정렬을 전부 순회할 때 드는 비용을 구합니다. 위에 문제보다 조금 난이도가 있으며 저는 개인적으로 왜 이게 골3인지 모르겠습니다. 단순히 사이클 확인에 우선순위 큐 쓰는 게 골드2인데...

9470번: Strahler 순서

저에게 위상 정렬의 존재를 깨닫개 해 준 문제입니다. 꼭 그렇지 않아도 개인적으로 위상 정렬을 이해하는 데 도움이 되는 문제라고 생각합니다. 저는 위상 정렬을 공부하기 전에 너비우선 탐색 + 다이나믹 프로그래밍 으로 문제를 풀었었는데, 코드의 길이는 위상정렬로 푼 코드의 길이보다 두 배나 더 길었었습니다.

3665번: 최종 순위

위상 정렬 응용 문제라는데 이건 저도 못풀어봤습니다. 풀려고 노력 중이구요, 쉽지가 않네여. 아마 풀게 되면 리뷰를 할 듯 합니다. (2022/08/06 추가) 풀었습니다. 간선의 일부가 변경된 그래프의 위상 정렬을 구하는 문제 입니다. 하지만 그래프 이론에 대해 빠삭하게 알고 있다면 위상 정렬을 사용하지 않고도 풀 수 있습니다.

마치며

틀린 부분이 있을 수 있으니 있으면 지적 부탁드립니다.