Leetcode 207. Course Schedule

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

Course Schedule - LeetCode

문제

주어지는 정수 numCourses 만큼의 강의가 존재한다. 각 강의는 0번 부터 numCourses -1번 까지 번호가 메겨져있다. prerequisites라는 배열이 함께 주어지는데 이는 prerequisites[i] = [a, b]로 이루어져 있으며 a는 강의 번호 b는 선수강 강의 번호를 의미한다.

 

예를 들어, [0 , 1]이 주어지면 0번 강의를 듣기위해서는 1번 강의를 들어야 함을 의미한다.

 

만약 모든 강의를 수강할 수 있다면 True를 그렇지 않다면 False를 반환하라

 

코드

class Solution:

    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:

        m = [[] for _ in range(numCourses)]

        for (c, r) in prerequisites:

            m[c] += [r]

        def isCycle(c, v):

            # print(c, end=" ")

            if c in v:

                return True

            for cc in m[c]:

                if isCycle(cc, v + [c]):

                    return True

            return False

        for i in range(numCourses):

            # print()

            if isCycle(i, []):

                return False

            m[i] = []

        return True

---

이번주 Leetcode 문제들은 모두 DFS로 구성되어 있는듯 하다. 내 스스로가 이렇게 말하면 그렇지만 문제를 풀면 풀 수록 DFS 함수의 짜임새가 날로 좋아지는 것 같아 뿌듯하다.