위상 정렬 (Topological Sorting)

• 기본 개념과 설명은 위키피디아에 잘 나와있다 - Topological Sorting

• 위상정렬 결과를 구하는 알고리즘은 Kahn's algorithm과 DFS를 이용하는 방법이 있다. 인접리스트로 그래프가 주어질때, 수행시간은 둘 다 O(|V|+|E|)이다.
  • 종만북에서는 Kahn's algorithm은 가볍게 언급만 하고 DFS 방법만 설명한다. 바킹독의 실전 알고리즘 강좌에서는 Kahn's algorithm을 설명한다
  • 여러 가지의 가능한 정렬 결과들 중, 특정한 순서를 만족하는 결과를 얻으려면 Kahn's algorithm 을 써야 한다.
  • 결과를 generator 형태로 얻으려면 Kahn's algorithm 을 써야 한다.
    • DFS에서는 위상정렬의 결과를 역순으로 구한 뒤에 reverse를 해서 최종 결과를 얻는 방식이라서 불가능하다.
  • DFS를 이용하는 방법을 구현할 때, 재귀 버전의 DFS을 사용한다면 간단하게 구현할수 있지만, 비재귀 버전의 DFS라면 좀 더 테크닉이 필요하다. 아래에 언급하는 python graphlib의 _find_cycle() 함수 구현을 참고하자.
• 방향그래프에서 사이클을 찾는 문제도 위상 정렬 알고리즘에 기반하여 해결할 수 있다.
  • Kahn's algorithm을 돌리다가, 모든 노드를 포함하는 위상정렬 결과가 만들어지기 전에 indegree가 0인 노드가 남아있지 않게 되면, 사이클이 있는 것이다
  • DFS에서는 탐색중인 노드들과, 탐색이 완료된 노드들을 따로 저장하면서 탐색하는 방식으로, 사이클이 발견되면 바로 찾을 수 있다.
  • 사이클의 존재 여부뿐 아니라, 그 사이클에 어떤 노드가 포함되었는지 정보까지 알기 위해서는 DFS 방식을 써야 한다
• Python 3.9에서는 TopologicalSorter 클래스를 포함하는 graphlib 모듈이 추가되었다.
  • 위상정렬 결과를 리턴해주고, 사이클이 있는 경우에는 그 사이클의 정보를 포함하는 예외를 발생시킨다.
  • 그러나, 아직 대부분의 PS사이트에서는 python 3.8을 사용하고 있기 때문에 사용이 가능해지려면 좀 기다려야 할 듯..
  • BOJ에서는 python 3.9를 쓰니까 사용 가능하다. 그리고 이미 Python 3.10의 릴리즈를 코앞에 둔 상황인데, 이쯤 되면 다른 사이트에서도 3.8은 이제 버리지 않을까 하는 기대를 해보면서, BOJ에서는 TopologicalSorter를 사용하기로 결정했다.
  • PS 사이트에서 못 쓰더라도, 소스코드가 순수 파이썬으로 작성되어 있어서 참고할만 하다. 위상정렬 코드는 패러럴 컴퓨팅까지 고려해서 좀 복잡하게 구현되어있으나, 비재귀 DFS에 기반한 사이클 디텍션은 따로 함수로 빠져있고, 구현도 심플해서 그대로 조금 변형해서 갖다 쓰는것도 가능할 듯.

• graphlib.TopologicalSorter 가 사용 가능한 환경에서는 가능한 그것을 이용해서 작성하자. 아래의 코드는 graphlib.TopologicalSorter를 쓸수 없는 환경(Python 3.8이하만 지원하는 사이트) 에서만 사용하도록 한다.

from typing import AbstractSet, List, Sequence


def topological_sort(graph: Sequence[AbstractSet[int]]) -> List[int]:
    """Returns a list of nodes in topologically sorted order."""
    indegrees = [0] * len(graph)
    for successors in graph:
        for v in successors:
            indegrees[v] += 1

    stack = [u for u, indegree in enumerate(indegrees) if indegree == 0]
    result = []
    while stack:
        u = stack.pop()
        result.append(u)
        for v in graph[u]:
            indegrees[v] -= 1
            if indegrees[v] == 0:
                stack.append(v)

    if len(result) != len(graph):
        raise ValueError('found a cycle')
    return result

• graphlib.TopologicalSorter 를 쓰면 거의 모든 활용 문제를 모두 처리할 수 있다.
• 전에는 python 3.9를 지원하는 사이트가 거의 없어서 안쓰려고 했었는데, 가능하면 무조건 쓰는 것으로 정책을 바꿨다. 코드량이 확 줄어든다.
• 범용적이다보니 속도는 직접 짠 알고리즘보다 오히려 좀 느리다. 먼저 cycle 체크를 한번 하고, 다시 위상 정렬을 돌리는 식으로 동작하므로 벌써 느리다. 하지만 큰 차이가 나는 것은 아니다. 열심히 사용하자
• 초기화하는 방식에는, 디펜던시 그래프를 만들어서 생성자로 넘기는 방법과, 그냥 디펜던시를 하나하나 add 메소드를 이용해서 추가하는 방법이 있다.
  • 그래프는 dict of iterable 형식이다. 튜토리얼 문서의 예시에는 dict of set 으로 되어있어서 꼭 그렇게만 만들어야 하는 것으로 오해할 수 있는데, dict of list 도 지원된다.
  • 초기화하는 것만 봤을때에는, 엣지들로 그래프를 만들어서 넘겨주는 것보다 그냥 엣지들을 바로 add 메소드로 추가해 주는 것이 더 효율적이다. 그러나 위상정렬 다음 단계의 작업에서 그래프가 어차피 필요한 경우도 종종 있는데, 이럴때는 어차피 그래프를 만들어야 하니, 이것으로 TopologicalSorter도 초기화해버리는 것이 낫다
• TopologicalSorter를 초기화 한 이후에는, 대부분의 경우는 static_order()을 돌려서 위상정렬 결과를 얻는 것으로 충분하다. 몇몇 경우에는 루프 안에서 get_ready()와 done()를 반복하면서 작업해야 하는 경우가 있긴 한데, 아래의 활용 문제 유형에서 설명한다. 또한 사이클 디텍션만이 목표라면 prepare() 만 돌려보면 된다.

• 위상 정렬 순서대로 출력하기
  • ⇒ 가장 기본. 노코멘트
• 사이클 존재 여부 찾기 (=가능한 정렬 순서가 존재하지 않는지 찾기)
  • ⇒ 위에서 설명한대로,
• 위상 정렬 순서가 유일한지 확인하기

• 위에서 언급했던대로, DFS기반으로는 처리할수 없고, Kahn's algorithm 의 경우에는 큐 대신 우선순위큐를 쓰는 방법으로 해결 가능하다.
• TopologicalSorter을 쓸 경우에는 static_order() 함수를 쓰는 대신에, 직접 루프를 돌면서 get_ready()와 done()를 반복해서 호출하는 식으로 처리하면 해결 가능하다.
• get_ready()를 호출해서 얻은 다음 방문 후보 노드들을 우선순위큐에 모두 저장하고, 우선순위큐에서 최소 노드를 꺼낸다음에 그 노드에 대해서 done()를 호출하는 것을 반복하는 방식으로 구현이 가능하다.
• 그냥 하나의 함수 안에서 이 작업을 같이 처리하는 것에 비하면 속도면에서 조금 비효율적일것 같지만, TopologicalSorter를 쓰는 것 자체가 이미 구현의 편의성을 위해서 속도상으로 페널티를 안고 가기로 한것이니만큼 별로 신경쓸필요 없다.
• 코드는 이런식이다

  • # graph = ...
    ts = graphlib.TopologicalSorter(graph)
    answer = []
    heap = []
    ts.prepare()
    while ts:
        for node in ts.get_ready():
            heapq.heappush(heap, node)
        cur_node = heapq.heappop(heap)
        answer.append(cur_node)
        ts.done(cur_node)
    return answer

• 임계 경로 (=최장 경로=선행 작업을 모두 처리한 후 특정 작업을 마치는 최단 시간)
• 최단경로 (DAG에서의 최단 경로는 다익스트라보다도 이 방법이 빠르다)
• 그외 온갖 잡다한 것들

• 위상 정렬
  • 음악프로그램
• 사이클 존재 여부 확인
  • Course Schedule
• 여러개의 가능한 위상 정렬 순서 중에서 특정 순서상 가장 빠른 것을 찾기 (e.g. 사전순으로 빠른 경로)
  • 문제집
• 위상 정렬 순서에 기반한 DP
  • 임계경로 - 임계경로