[TIL_Carrotww] 97 - 23/02/08

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode 207 Course Schedule - Medium

문제를 이해하는데 오래 걸렸다.
무슨 소리인가 했는데 간단했다.
순환 구조가 나오면 False, 아니라면 True를 리턴하면 된다.

• 풀이

class Solution:
    def canFinish(self, numCourses: int, pre: List[List[int]]) -> bool:
        from collections import defaultdict

        graph = defaultdict(list)

        for start, end in pre:
            graph[start].append(end)

        path, visited = set(), set()

        def dfs(node):
            if node in path:
                return False
            if node in visited:
                return True

            path.add(node)
            for start in graph[node]:
                if not dfs(start):
                    return False

            path.remove(node)
            visited.add(node)
            return True

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

        return True