LeetCode 207. Course Schedule

파이썬 알고리즘 인터뷰 문제 39번(리트코드 207번) Course Schedule
https://leetcode.com/problems/course-schedule/

나의 풀이(미해결, Time Limit Exceeded)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        result = [True]

        for a, b in prerequisites:
            graph[a].append(b)
            graph[b]
        
        #for x in graph:
        #    print(graph[x])

        def helper(course, path):
            #print(course, path, result)
            if not graph[course]:
                return
            for prerequisite in graph[course]:
                if prerequisite in path:
                    result[0] = False
                    #print('a', course, path, result)
                    return
                else:
                    path.append(prerequisite)
                    helper(prerequisite, path)
                    path.pop()
                
        
        for course in graph:
            helper(course, [])
        
        return result[0]

다른 풀이1(DeepSeek)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)  # b -> a
        
        visited = [0] * numCourses  # 0: 방문 안 함, 1: 방문 중, 2: 방문 완료
        
        def has_cycle(course):
            if visited[course] == 1:  # 사이클 발견
                return True
            if visited[course] == 2:  # 이미 방문 완료
                return False
            
            visited[course] = 1  # 현재 방문 중 표시
            for neighbor in graph[course]:
                if has_cycle(neighbor):
                    return True
            visited[course] = 2  # 방문 완료 표시
            return False
        
        for course in range(numCourses):
            if has_cycle(course):
                return False
        
        return True

다른 풀이2(책 풀이)

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

        for a, b in prerequisites:
            graph[a].append(b)
        
        def has_cycle(course):
            if course in trace:
                return True
            if course in visited:
                return False
            trace.add(course)
            for neighbor in graph[course]:
                if has_cycle(neighbor):
                    return True
                # 오답1. return has_cycle(neighbor) 하면 안됨.
            trace.remove(course)
            visited.add(course)
            return False
        
        for course in list(graph): # 오답2. 그냥 graph로 에러 발생.
            if has_cycle(course):
                return False
        
        return True

오답 및 배울점

• 재귀, 백트래킹은 참 알다가도 모르겠다.
• 이제 익숙해졌다고 생각했는데 또 스스로 못 풀었다.
• 어렵다 어려워.

오답1

• if has_cycle(neighbor) then return True대신 return has_cycle(neighbor)하면 틀린다.
• 1-> [2, 3]
• 2-> []
• 3 -> [1]
• 으로 생겼다고 하자. 그러면 1↔3으로 cycle이 있다.
• 그런데 1 이웃으로 2를 검사하게 되고 2는 이웃이 없으므로 False를 반환하게 된다. 그러면 1 도 False를 반환하게 된다. 하지만 1 은 이웃 3 과 cycle을 이룬다. 이는 1의 이웃인 2, 3을 모두 검사하기 전에 2 만 검사하고 False를 반환하기 때문이다.
• 그러니까 모든 이웃을 검사하기 전에 cycle 발견되었을 때는 나머지 이웃을 검사하지 않고 True를 반환하면 되지만, cycle 없다고 하려면 모든 이웃을 검사해야 한다.

오답2

• for course in graph로 순회하면 RuntimeError: dictionary changed size during iteration 에러 발생
• 왜냐하면 그래프를 생성할 때 graph[a]=b 와 같은 방법으로 생성했으므로, b 는 key로 없을 수 있다. 이때, defaultdict으로 생성했으므로 graph[b]를 하는 순간 빈 리스트로 초기화 되어 graph의 key가 하나 늘어난다. for문으로 순회하며 key가 늘어나기 때문에 이런 에러가 발생한다. 이런 일이 일어나는 것은 has_cycle(neighbor) 에서 neighbor이 key로 없기 때문이다.
• 대처 방안은 두 가지로, 풀이에 써둔 것처럼 list(graph) 로 key를 list로 복사하여 순회하는 방법이 있고, 그래프를 생성할 때, 아래와 같이 graph[a].append(b) 와 graph[b]를 모두 하는 방법이 있다.

        for a, b in prerequisites:
            graph[a].append(b)
            graph[b] # <- 미리 초기화하여 두기.

• 무튼 재귀와 백트래킹은 어렵다. 복습 꼭 하기.