[LeetCode] Python - 207. Course Schedule

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

Course Schedule - LeetCode

생각

예전에 SWEA에서 비슷한 문제를 풀었던것 같은데 다시 풀어도 어려운 문제같습니다.

DFS +백트래킹으로 노드들을 탐색했습니다. 선수 과목을 들어야만 다음 과목을 들을 수 있기 때문입니다. (위상 정렬을 통해 문제를 풀 수 있다고 합니다.)

 

1. prerequisites에 대한 dictionary 정보를 만들어줍니다. { 선수과목 : [다음과목1, 다음과목2, ...] }

2. numCourses 만큼 반복문을 돌면서 DFS 탐색을 시작합니다. 

3. 현재 과목에 대한 방문체크를 해줍니다.

3. 선수과목에 대한 후수과목들을 들을 수 있는지 모든 경우를 탐색해주기 위해 재귀호출을 합니다.

4. 이때 싸이클이 발생한다면 False를 리턴시켜줍니다. 더 이상 갈 곳이 없으면 탐색이 올바르게 된것이므로 True를 리턴시켜줍니다.

5. 탐색한 수업들에 대해 remove를 해줍니다. 여기서 remove를 해주지 않으면 방문했던 수업들이 계속 남아있어, 사이클이 발생할 수 있다고 잘못 판단할 수 있기 때문입니다.

6. 선수과목에 대한 DFS 탐색이 성공적으로 완료된 경우에는 위와 같은 작업을 반복할 필요가 없으므로, preMap[현재수업] 도 빈 리스트로 초기화 시켜줍니다. 이렇게 하면 기저조건인 preMap[cur] == [] : return True 에서 바로 리턴될 수 있습니다. -> (백트래킹)

 

Python Code

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        preMap = {x:[] for x in range(numCourses)}
        for before,after in prerequisites:
            preMap[before].append(after) 
    
        visit = set()
        
        def dfs(cur):
            # 사이클 발생하면 False
            if cur in visit:
                return False
            # 더이상 갈곳이없으면 true
            if preMap[cur] == []:
                return True
            
            visit.add(cur)
            
            # dfs로 갈수있는경우 모두 탐색
            for pre in preMap[cur]:
                if not dfs(pre):
                    return False
            visit.remove(cur)
            preMap[cur] = []
            return True
                    
        for course in range(numCourses):
            if not dfs(course):
                return False
        return True