====== 위상 정렬 (Topological Sorting) ======

  * 기본 개념과 설명은 위키피디아에 잘 나와있다 - [[https://en.wikipedia.org/wiki/Topological_sorting|Topological Sorting]]

  * 위상정렬 결과를 구하는 알고리즘은 [[https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm|Kahn's algorithm]]과 DFS를 이용하는 방법이 있다. 인접리스트로 그래프가 주어질때, 수행시간은 둘 다 O(|V|+|E|)이다.
    * 종만북에서는 Kahn's algorithm은 가볍게 언급만 하고 DFS 방법만 설명한다. [[https://blog.encrypted.gg/910?category=773649|바킹독의 실전 알고리즘 강좌]]에서는 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 클래스를 포함하는 [[https://docs.python.org/3.9/library/graphlib.html|graphlib 모듈]]이 추가되었다.
    * 위상정렬 결과를 리턴해주고, 사이클이 있는 경우에는 그 사이클의 정보를 포함하는 예외를 발생시킨다.
    * <del>그러나, 아직 대부분의 PS사이트에서는 python 3.8을 사용하고 있기 때문에 사용이 가능해지려면 좀 기다려야 할 듯..</del>
    * BOJ에서는 python 3.9를 쓰니까 사용 가능하다. 그리고 이미 Python 3.10의 릴리즈를 코앞에 둔 상황인데, 이쯤 되면 다른 사이트에서도 3.8은 이제 버리지 않을까 하는 기대를 해보면서, BOJ에서는 TopologicalSorter를 사용하기로 결정했다.
    * PS 사이트에서 못 쓰더라도, [[https://github.com/python/cpython/blob/3.9/Lib/graphlib.py|소스코드]]가 순수 파이썬으로 작성되어 있어서 참고할만 하다. 위상정렬 코드는 패러럴 컴퓨팅까지 고려해서 좀 복잡하게 구현되어있으나, 비재귀 DFS에 기반한 사이클 디텍션은 따로 함수로 빠져있고, 구현도 심플해서 그대로 조금 변형해서 갖다 쓰는것도 가능할 듯.

===== 코드 =====
  * graphlib.TopologicalSorter 가 사용 가능한 환경에서는 가능한 그것을 이용해서 작성하자. 아래의 코드는 graphlib.TopologicalSorter를 쓸수 없는 환경(Python 3.8이하만 지원하는 사이트) 에서만 사용하도록 한다.
<dkpr py>
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
</dkpr>

===== TopologicalSorter =====
  * 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() 만 돌려보면 된다.


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

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

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

===== 관련 문제 =====
  * 위상 정렬
    * [[:ps:problems:boj:2623|음악프로그램]]
  * 사이클 존재 여부 확인
    * [[:ps:problems:leetcode:207|Course Schedule]]
  * 여러개의 가능한 위상 정렬 순서 중에서 특정 순서상 가장 빠른 것을 찾기 (e.g. 사전순으로 빠른 경로)
    * [[:ps:problems:boj:1766]]
  * 위상 정렬 순서에 기반한 DP
    * 임계경로 - [[:ps:problems:boj:1948]]