207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

My Answer 1: Wrong Answer (40 / 46 test cases passed.)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if len(prerequisites) == 1:
            return True
        
        if len(prerequisites) == 0:
            return True
        
        course = []
        
        for a, b in prerequisites:
            if [b, a] in prerequisites:
                return False
            if a in course and b in course and course.index(a) < course.index(b):
                continue
            if a in course:
                course.append(b)
            elif b in course:
                course.insert(0, a)
            else:
                course.append(a)
                course.append(b)
                
        course2 = course[len(course)//2:]
        
        for i in range(0, len(course)//2):
            if course[i] in course2:
                return False
        
        return True

cycle 이 있으면 무조건 False 라 생각해서

과목 이수 순서대로 리스트에 넣고 리스트를 반으로 나눠서
왼쪽 반에 있는 값이 오른쪽 반에도 있으면 False 리턴하도록 하는 방식도 생각했지만.. 안됨;

My Answer 2: Wrong Answer (32 / 46 test cases passed.)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        course = {}
        
        for a, b in prerequisites:
            course[a] = b
            
        for key, val in course.items():
            if val in course and course[val] == key:
                return False
        
        return True

이번엔 딕셔너리를 이용해서 해보려했지만 안됨..

루션아 나와!!!

Solution 1: Runtime: 88 ms - 96.29% / Memory Usage: 17.5 MB - 19.08%

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i:[] for i in range(numCourses)}
        for course,pre_course in prerequisites:
            graph[course].append(pre_course)
            
        # whether exist circle
        def DFS(course,seen):
			# if node have been traveled
            if seen[course]==0:
                return False
            elif seen[course]==1:
                return True
            
            seen[course] = 1
            for pre_course in graph[course]:  
                if DFS(pre_course,seen):
                    seen[course] = 0
                    return True
            seen[course] = 0
       
            return False
			
        seen = {i:-1 for i in range(numCourses)}    
        for course in range(numCourses):         
            if DFS(course,seen):
                return False
        return True

그나마 이해하기 좋아보이는 걸로 가져왔다.
근데 이해 안됨..^^

graph 랑 seen 을 이용하는 DFS 방식인데...
선수 과목을 확인한적 있으면 최종적으로 False 를 리턴하는건가...??