[python/leetcode]course schedule/tree/dfs

문제

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

 

코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        # tuple뿐만 아니라 list도 x, y = list 가능
        for x, y in prerequisites:
            graph[x].append(y)
        
        visited = set()
        ok = set()
        def dfs(i):
            if i in visited:
                return False
            if i in ok:
                return True
            
            visited.add(i)
            for y in graph[i]:
                # dfs에서 False가 나온 경우(이미 방문한 적이 있는 경우) False
                if not dfs(y):
                    return False
            visited.remove(i)
            
            ok.add(i)
            return True
            
        for x in list(graph):
            if not dfs(x):
                return False
        return True
            

1. 그동안 tuple만 x, y = tuple식으로 사용할 수 있는 줄 알았는데, list도 x, y= list라고 바로 사용할 수 있다는걸 알게 됐다. 앞으로 코드를 좀 더 가독성 좋게 작성할 수 있을 것 같다. 

 

2. dfs문제는 defaultdict에 key, value를 넣어서 그래프를 만들어주고, 그래프의 노드를 방문하면서 계산을 한두개씩 해주는 문제인 것 같다. 이제야 슬슬 감이 오는 기분이다.