207. Course Schedule (Depth-First Search, Breadth-First Search, Graph, Topological Sort)

링크 - https://leetcode.com/problems/course-schedule/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Topological Sort Using Kahn's Algorithm

우리는 각 코스마다 필수요건코스들이 있는 코스들이 있는 것을 알고있다. 따라서 우리는 일차원 배열과 이차원배열 두가지를 가지고 deque를 활용해 문제를 풀어야 한다.

1. 일차원 배열 num_prerequisites_per_course를 [0] * numCourses로 초기화 한다. 그리고 각 인덱스(코스)에는 필요한 prerequisites 코스개수를 값으로 넣는다.

2. 이차원 배열 num_courses_after_prerequisite을 [[] for _ in range(numCourses)]로 초기화 한다. 그리고 각 인덱스 (코스)에는 그 이후에 들을 수 있는 course들의 값들을 배열로 넣는다.

3. deque를 통해 먼저 num_prerequisites_per_course가 0인 인덱스들을 먼저 append한다.(prerequisite이 없는 코스들을 큐에 먼저 넣는것과 같은 의미)

4. while문을 통해 deque가 비어있을때까지 돌린다. deque.popleft()를 통해 course를 가져오고, 그 코스의 다음 코스들을 num_courses_after_prerequisite을 통해 불러온다. 그 다음 코스들의 num_prerequisites_per_course값을 1씩 줄이고, 만약 0이되면 queue에 append한다.

5. while문을 다 돌면 들을 수 있는 모든 코스들의 개수를 알고있다. 이게 numCourses와 같은지 비교한다.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        num_prerequisites_per_course = [0] * numCourses
        num_courses_after_prerequisite = [[] for _ in range(numCourses)]

        for p in prerequisites:
            num_prerequisites_per_course[p[0]] += 1
            num_courses_after_prerequisite[p[1]].append(p[0])

        queue = deque()
        for c in range(numCourses):
            if num_prerequisites_per_course[c] == 0:
                queue.append(c)

        num_visited_courses = 0
        while queue:
            course = queue.popleft()
            num_visited_courses += 1

            for after_course in num_courses_after_prerequisite[course]:
                num_prerequisites_per_course[after_course] -= 1
                if num_prerequisites_per_course[after_course] == 0:
                    queue.append(after_course)

        return num_visited_courses == numCourses

n = 코스의 개수, m = prerequisites의 사이즈

Time Complexity: O(m+n) num_courses_after_prerequisite를 만드는데 O(m)이 소요된다. 그리고 queue에서 코스들을 불러오는데 O(n)이 소요된다. 

Space Complexity: O(m+n)

2) DFS

우리는 매 코스마다 dfs를 돌리는 방법을 생각해 볼 수 있다. 알고리즘은 다음과 같이 동작한다.

1. courses_after_prerequisite 2차원 배열은 만들어서 각 코스를 듣고난 뒤에 들을 수 있는 코스들을 저장한다. 

2. visit과 inStack 1차원 boolean type 배열을 만든다. visit은 들은 코스들을 tracking하고, inStack은 cycle를 감지하는데 쓴다. 

3. 각 코스마다 DFS를 돌린다. 각 DFS operation은 graph에 cycle이 있는지를 결과로 boolean을 반환한다. 만약 cycle이 감지되면 우리는 곧바로 False를 답으로 반환해야 한다. 하지만 cycle이 없다면, 우리는 마지막에 True를 통해 모든 코스들을 들을 수 있다고 반환한다.

3.1 만약 inStack[course]가 True이면, dfs는 cycle에 있으므로 바로 True를 반환한다.

3.2 만약 visit[course]가 True이면, 우리는 이전에 dfs를 통해 cycle이 없는걸 확인했으므로 False를 반환한다.

3.3. inStack[course] 과 visit[course] 모두 True로 설정한다. 

3.4 이 코스 다음에 들을 수 있는 코스들을 courses_after_prerequisite[course]를 통해 얻는다. 그 코스들도 dfs를 돌린다.

3.5 dfs를 돌리고 나면 inStack[course]를 False로 설정해 dfs를 끝낸다.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        courses_after_prerequisite = [[] for _ in range(numCourses)]
        for p in prerequisites:
            courses_after_prerequisite[p[1]].append(p[0])

        visit = [False] * numCourses
        inStack = [False] * numCourses
        for i in range(numCourses):
            if self.isDfsCycled(i, courses_after_prerequisite, visit, inStack):
                return False
        return True

    def isDfsCycled(self, course, courses_after_prerequisite, visit, inStack):
        if inStack[course]:
            return True
        if visit[course]:
            return False

        visit[course] = True
        inStack[course] = True
        for next_course in courses_after_prerequisite[course]:
            if self.isDfsCycled(next_course, courses_after_prerequisite, visit, inStack):
                return True
        inStack[course] = False
        return False

Time Complexity: O(m+n) courses_after_prerequisite를 만드는데 O(m)이 소요된다. 그리고 queue에서 코스들을 불러오는데 O(n)이 소요된다.

Space Complexity: O(m+n)