[Leetcode] 207. Course Schedule

문제 바로가기

Topological Sort (위상 정렬)

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다.

출처: Wikipedia

Kahn's algorithm

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

반복

1. 진입 차수가 0인 정점 선택
2. 간선을 지우고 연결된 정점들의 진입 차수 업데이트

만약 모든 간선이 지워지지 않는다면 return false

풀이

Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$

from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # a dictionary for outgoing edges.
        # { key: prerequisite, value: the list of courses }
        outgoing = defaultdict(list)
        # the number of incoming edges. if key does not exist, 0.
        num_incomings = defaultdict(int)
        for cour, prereq in prerequisites:
            outgoing[prereq].append(cour)
            num_incomings[cour] += 1
        
        cours_w_prereq = num_incomings.keys()
        cours_wo_prereq = [ i for i in range(numCourses) if i not in cours_w_prereq ]
        queue = deque(cours_wo_prereq)
        
        while queue:
            front = queue.popleft()
            for cour in outgoing.pop(front, []):
                num_incomings[cour] -= 1
                if num_incomings[cour] == 0:
                    queue.append(cour)
        
        return False if outgoing else True

참고 및 출처

• [Wikipedia] 위상 정렬 - 바로가기