[LeetCode] 207. Course Schedule [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Course Schedule - LeetCode>

1. 문제 (코스 스케줄)

[0, 1]로 구성된 스케줄로 0을 수강하기 위해서는 1을 선수강해야하는 n개의 코스가 있다.

코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.

2. 풀이

DFS를 이용한 풀이

3. 코드

from collections import defaultdict
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        traced, visited = set(), set()

        for x, y in prerequisites:
            graph[x].append(y)

        def dfs(idx):
            if idx in traced:
                return False
            if idx in visited:
                return True

            traced.add(idx)

            for y in graph[idx]:
                if not dfs(y):
                    return False

            traced.remove(idx)
            visited.add(idx)
            return True

        for x in list(graph):
            if not dfs(x):
                return False

        return True

• 결과 :

방식	Status	Runtime	Memory	Language
그래프 (DFS)	[Accepted]	164 ms	17.7 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋