207. Course Schedule

import collections

class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(list)

        # graph에 싹 다 넣어주고
        for x, y in prerequisites:
            graph[x].append(y)

        def dfs(destination):
            # 현재 지나왔던 곳으로 다시 돌아가는거면 순환 구조니까 False임
            if destination in cur_route:
                return False

            # 목적지가 visitied에 들어가있으면 해당 목적지에 대한 계산은 이미 끝난거니 True임
            # 만약에 해당 목적지에 대해서 순환 구조면 False 리턴해서 여기 오지도않음
            if destination in visited:
                return True

            # 현재 방문하고 있는 곳들을 넣어줌
            cur_route.append(destination)

            # 방문하면 넣어줌
            visited.append(destination)

            # 현재 목적지를 완료 하기 위해서는 필요한 코스들을 전부 완료해야하니 싹 다 봐줌
            for courses in graph[destination]:
                if not dfs(courses):
                    return False

            # 이 목적지에 대해서 체크를 다했으니 빼줌
            cur_route.remove(destination)

            return True

        cur_route = []
        visited = []
        # 이거 list 
        for destination in list(graph):
            # 중간에 순환 구조 나오면 False임
            if not dfs(destination):
                return False

        # 다 돌았는데 순환 구조 없으면 True임
        return True

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