[medium] 207. Course Schedule

문제

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

---

풀이방법

course의 prerequisites를 탐색하다가 순환이 존재하는지를 찾는 문제이다.

• prerequisites 리스트를 그래프로 만든다. 파이썬에서는 dict 구조 활용
• 각 course에 해당하는 graph를 탐색하다가 순환이면 탐색을 중단하고 False를 리턴. 그렇지 않으면 graph 탐색을 계속한다
  1. 순환인지 여부를 찾기 위해서는 course와 그에 해당하는 prerequisites를 history로 관리해야한다. 그래프 탐색 과정에서 현재 course가 이미 history에 있으면 순환이다
  2. 그래프 탐색과정에서 순환이 아닌 course들은 이미 검증이 완료되었음을 저장해두었다가, 다시 탐색할 일이 없도록 해야 시간을 절약할 수 있다
  3. 그래프 탐색과정에서 순환이 아닌 것으로 판별된 course들은 이미 검증이 완료되었음을 저장해두었다가, 다시 탐색할 일이 없도록 해야 시간을 절약할 수 있다

반응형

---

코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        ret = True
        prereq = {}
        self.saved = [False] * numCourses
        
        for a,b in prerequisites:
            if a in prereq.keys():
                prereq[a].append(b)
            else:
                prereq[a] = [b]
        
        def search(course, history):
            if self.saved[course]:
                return True
            
            if course in history:
                self.saved[course] = False
                return False
                
            history.append(course)
            if course in prereq.keys():
                for newcourse in prereq[course]:
                    if self.saved[newcourse]:
                        continue
                    if search(newcourse, history) == False:
                        return False
                    
            self.saved[course] = True
            return True
        
        for course in range(numCourses):
            if self.saved[course]:
                continue
            history = []
            ret = search(course, history)
            if ret == False:
                return ret
            self.saved[course] = True
        return ret