[LeetCode] 207. Course Schedule

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

수강해야하는 총 numCourses 과정이 있으며, 0부터 numCourses-1. 레이블이 지정되어 있습니다. prerequisites [i] = [ai, bi]는 수강하려면 먼저 과정 bi를 수강해야 함을 나타냅니다. 모두 수강할 수 있는지 구하세요.

✍️ 풀이

---

어떤 과목을 수행하려면 선행과목이 존재한다. 그런데 이 두개가 서로가 서로의 선행과목 이라면 순환이 생겨 문제가 발생한다. 이를 해결하는 문제이다.

가장 기본적인 방법은 방문했던 노드를 체크하는 것이다. 한번 방문한 노드는 다시 방문하지 않는다면 순환을 해결할 수 있다. 성능을 더 높이기 위해서는 방문했던 노드는 True로 반환한다면 순환 검사를 중복으로 검사하지 않으므로 성능을 더욱 높일 수 있다.

코드에서 traced는 현재까지 거친 과목들이 들어있고 visited는 방문 후 순환 검사까지 완료한 노드가 들어가게 된다.
따라서, traced에 중복된 과목이 있으면 순환으로 False를 반환하고, visited에 중복된 과목이 있으면 이미 검사해서 굳이 검사할 필요가 없으므로 바로 반환하도록 한다.

🛠 코드

---

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # defaultdict 순회 문제 시 전혀 값을 건들지 않았는데 값을 바꿨다고 나올 수 있다.
        # 그 이유는 defaultdict가 빈 값 조회시 null말고 디폴트를 생성하므로 나는 오류이다.
        graph = collections.defaultdict(list)


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

        traced = set() # 중복 노드를 검사해서 사이클을 검사하는 집합
        visited = set() # 이미 방문한 즉, 이미 검증된 노드를 기록하는 집합
        # visited로 가지치기가 가능해져 속도의 엄청난 향상을 가져옴.

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

            traced.add(i)

            for y in graph[i]: # 빈 값 조회시 빈 리스트가 생성되긴 한다. 따라서 딕셔너리가 바뀌는 것이다.
                if not dfs(y):
                    return False
            traced.remove(i)

            visited.add(i)
            return True

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

        return True

---

📝 정리

---

🎈 참고

---

Book 링크