위상정렬 (topological sorting)

위상정렬 (topological sorting)은 DAG에서 DFS 탐색 순서대로 노드의 값을 나열하는 것을 말한다. DFS는 어느 source 노드를 먼저 탐색할지를 임의로 정할 수 있기 때문에 다양한 위상정렬이 있을 수 있지만 '탐색 순서대로' 라는 규칙은 맞아야 한다. 일반적인 해법은 각 노드에 대해 탐색 상태를 저장하는 배열을 하나 만들고, DFS를 하면서, 배열에 다음과 같이 값을 기록한다.

• state 0 (white) : 노드가 아직 처리되지 않음
• state 1 (light gray) : 노드가 처리되는 중임(visiting)
• state 2 (dark gray) : 노드가 처리 완료 됨(visited)

처리 완료라는 말은 모든 후속 노드가 처리가 되었다는 뜻이다. 그럼 모든 후속 노드가 처리되었는지를 알려면 후속 노드들을 이미 처리 시도하였고 다 방문했다는 말이며, dfs 재귀 호출에서 base case를 모두 달성했다는 뜻이다. 즉, 더 이상 방문할 후속노드가 없는 경우, 현재 노드는 처리가 완료된 것으로 보며, 이 경우 (state 2) 현재 노드의 값을 위상정렬 결과를 저장하는 다른 배열에 추가한다. 그리고 현재 재귀함수는 나를 호출한 함수로 탐색을 마쳤다는 메시지를 전달하며 돌아가고, 나를 호출한 함수는 모든 피호출 함수들이 DFS 탐색이 완료되었을 때 역시 자신의 함수의 인수인 노드에 대해 처리 완료(2)로 마크하고 또한 그 노드 값 자체를 결과 배열에 저장한다. 나중에 결과 배열은 방문의 역순이므로 이를 뒤집어 보고하면 된다.

그런데 만일, 처리를 위한 탐색 과정 중에 사이클이 발견되었다면? 위상정렬은 불가능하다. 이를 검증하기 위해 state 1 을 설정해 놓는 것이다. 즉, DFS로 미방문 노드 (state = 0) 를 방문 시도하게 되면, 방문중이라는 의미로 해당 노드를 state = 1로 바꾼다. 그런데, 노드의 인접 노드들을 방문하는 와중에, 방문대상 노드를 확인해 보니 state = 1 인 것이 있다면, 사이클이 있다는 의미이다. 미방문에서 출발하고 만일 사이클이 없다면 (한 노드에 두 번 방문하는 경우가 없다면), 그 후속 노드들은 모두 미방문 상태여야 하기 때문이다. 이해가 안된다면, 새로 포장한 도로에 경계 표시용 흰색 페인트를 칠하는 인부가 있다고 해보자. 이 구역은 단절되어 있고, 페인트 칠하는 인부는 나밖에 없다. 이제 일을 시작해서, 검은 도로에 페인트 칠하는 차를 타고 서서히 간다. 도로는 모두 검은색이다. 그런데 갑자기 흰색 페인트 칠한 도로가 나타났다. 인부는 뭐라고 생각할까. "아, 내가 아까 여길 칠했구나." 이게 바로 사이클이 있는 것이다. 두 번 왔기 때문이다.

그러면 알고리즘을 정리하면,

사이클이 있다 : 위상정렬 불가능하다고 보고
사이클이 없다 : 위상정렬 결과를 보고

참고로, 사이클 탐색에 있어 더 빠른 알고리즘은 two pointer 를 이용한 Floyd 의 것이 있고, 더 작은 메모리 공간 O(1)을 활용하며, linked list 의 사이클을 찾을 때도 사용될 수 있다.

관련문제

https://leetcode.com/problems/course-schedule/

Course Schedule - LeetCode

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = collections.defaultdict(list)
        for u, v in prerequisites:
            adj[u].append(v)
        states = [0 for _ in range(numCourses)]
        res = []
        def dfs(u):
            if states[u] == 1:
                return True
            states[u] = 1
            for v in adj[u]:
                if states[v] != 2 and dfs(v):
                    return True # cycle
            states[u] = 2
            return False
        
        for u in range(numCourses):
            if states[u] == 0:
                if dfs(u):  # True, cycle
                    return False  # cycle
        
        return True  # no cycle

https://leetcode.com/problems/course-schedule-ii

Course Schedule II - LeetCode

보통의 위상정렬은 방문하는 순서대로 출력해야 하는데, 이 문제는 약간의 tweak이 있다. 애초에 DAG의 화살표 방향이 후수과목 -> 선수과목 순이 되도록 입력자료가 구성되어 있고, 출력 요구사항은 과목을 듣는 순서대로이기 때문에, 굳이 마지막에 뒤집기를 하지 말아야 한다.

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # input, states: not visited (0),  visiting (1),  visited (2)
        adj = collections.defaultdict(list)
        for u, v in prerequisites:
            adj[u].append(v)
        states = [0 for _ in range(numCourses)]
        
        # cycle : True
        res = []
        def dfs(u):
            if states[u] == 1:
                return True
            states[u] = 1   # 0 -> 1
            for v in adj[u]:
                if states[v] != 2: #0 1
                    if dfs(v): # cycle
                        return True
            states[u] = 2
            res.append(u)
            return False
        
        # output
        iscycle = False
        for u in range(numCourses):
            if states[u] == 0:
                if dfs(u):
                    iscycle = True
                    break
        
        return res if not iscycle else []

https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/

Find All Possible Recipes from Given Supplies - LeetCode

https://leetcode.com/problems/count-good-meals/

Count Good Meals - LeetCode

https://leetcode.com/problems/alien-dictionary/

Account Login - LeetCode