[LeetCode] 210. Course Schedule II (Python)

안녕하세요~~ 오늘은 리트코드 210. Course Schedule 2 문제를 풀어보겠습니다.

 

0부터 numCourses-1 로 label되어 있는 총 numCourses 개의 강의를 들어야하는데, 선수과목이 존재합니다. 주어진 prerequisites 배열에서 prerequisites[i] = [ai, bi] 는 ai라는 과목을 듣기 위해서는 bi가 선수강되어야한다는 것을 의미합니다. 모든 Courses를 수강하기 위한 수강 순서를 출력하면 됩니다. 이 때, 여러 개의 답 중 유효한 답을 하나 출력하면 되고, 만약 답이 존재하지 않는다면 빈 array를 출력하면 됩니다. 

저는 DFS를 활용한 위상 정렬을 통해 문제를 풀어보겠습니다. 먼저 각 코스 별 후행 코스를 딕셔너리 형태로 만들어줍니다. 이후 방문 상태를 저장하기 위한 리스트를 만들고, dfs 함수를 정의하여 그래프 내 cycle을 감지하고 순서를 저장해줍니다. 모든 courses에 대해 dfs를 수행하고 cycle이 발견될 경우 빈 배열을 반환, cycle이 없다면 저장된 순서를 역순으로 출력해줍니다. 

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        # 각 코스 별로 후행 코스를 저장한 딕셔너리 생성
        graph = {i: [] for i in range(numCourses)}
        for course, precourse in prerequisites:
            graph[precourse].append(course)

        # 방문 상태 저장하기 위한 리스트 (0: 미방문, 1: 방문 중, 2: 방문 완료)
        check = [0] * numCourses
        order = []

        # cycle이 생기면 impossible이므로 빈 리스트 출력
        self.has_cycle = False  

        # DFS를 사용하여 사이클을 감지하고 순서를 찾는 함수
        def dfs(course):
            if check[course] == 1:  # 방문 중인 노드를 다시 방문 -> 사이클
                self.has_cycle = True
                return
            if check[course] == 2:  # 이미 방문 완료된 노드 -> 다시 방문할 필요 없음
                return

            # 현재 노드를 방문 중으로 표시
            check[course] = 1
            for next_course in graph[course]:
                dfs(next_course)
                if self.has_cycle:  # 사이클이 발견되면 탐색 종료
                    return

            # 현재 노드를 방문 완료로 표시하고 order에 추가
            check[course] = 2
            order.append(course)

        # 모든 courses에 대해 DFS 수행
        for i in range(numCourses):
            if check[i] == 0:  
                dfs(i)
            if self.has_cycle:  # 사이클이 있는 경우 빈 배열 반환
                return []

        # 탐색이 완료된 코스들이 뒤에서부터 추가되므로 순서를 뒤집어서 반환
        return order[::-1]

이 방법은 노드와 간선을 한 번씩 탐색하므로 시간 복잡도는 O(N+M)으로 표현할 수 있습니다. 여기서 N은 코스 수, M은 prerequisities의 수입니다. 

---

문제 풀이에 필요했던 알고리즘 개념들을 정리해보겠습니다.

* Directed Acyclic Graph (DAG)

방향이 있는, 사이클이 없는 그래프

* Topological Sort 위상정렬

DAG에서 노드 간의 선행 관계를 만족하는 순서대로 노드를 정렬하는 것을 의미. 이 문제에서처럼 선행과목이 있는 경우 등 선행 작업, 후행 작업이 있는 경우, 위상 정렬을 통해 수행 순서를 결정할 수 있다.