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

링크 - https://leetcode.com/problems/course-schedule-ii/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-three-months

난이도 - Medium

Intuition

우리는 이 문제를 DFS로 풀 수 있다. 푸는 방법은 다음과 같다.

1. 먼저 각 코스의 prerequisites의 개수를 나타내는 1차원 배열과, 코스들의 prerequisite관계를 나타내는 graph를 만든다.

2. 다음으로 답으로 반환할 빈 list와 방문한 course를 넣을 set을 만든다.

3. course를 돌면서 prerequisite개수가 0인 것에 대해서 dfs를 진행한다. dfs를 진행할때는 현재 진행하는 course를 ans에 미리 넣어둔다.

4. dfs를 할때는 현재 노드의 다음 prerequisite 개수를 1 줄여준다. 만약 0이 되고 visited안에 없으면, 우리는 dfs를 진행한다.

5. ans에 들어있는 course의 개수가 numCourses와 같으면 ans를 반환하고, 아니면 빈 list를 반환한다.

Code

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        num_prerequisites_per_course = [0] * numCourses
        graph = defaultdict(list)
        for p in prerequisites:
            num_prerequisites_per_course[p[0]] += 1
            graph[p[1]].append(p[0])

        def dfs(course):
            for next_course in graph[course]:
                num_prerequisites_per_course[next_course] -= 1
                if num_prerequisites_per_course[next_course] == 0 and next_course not in visited:
                    visited.add(next_course)
                    ans.append(next_course)
                    dfs(next_course)


        ans = []
        visited = set()
        for i in range(numCourses):
            if num_prerequisites_per_course[i] == 0 and i not in visited:
                visited.add(i)
                ans.append(i)
                dfs(i)

        return ans if len(ans) == numCourses else []

Complexity

여기서 V는 vertices의 개수이고, E는 edge의 개수이다.

Time Complexity: O(V+E) 우리는 dfs로 하면서 각 vertex와 node를 한번씩만 방문한다.

Space Complexity: O(V+E)