greentea31's Note

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

풀이 과정

어떤 지점을 방문하기 위해 방문해야 하는 선행 방문 지점이 주어질 때, 주어진 코스가 순회 가능한지 여부를 구하는 문제이다.

예를 들어 1을 방문하기 위해서 0을 방문해야 하고, 0을 방문하기 위해서 1을 방문해야 한다면, 두 지점 모두 방문이 불가능하므로 코스가 순회가 불가능하다고 할 수 있다.

문제에서 주어진 prerequisites를 그래프의 간선으로 생각해 그래프로 모델링 한 후, 그래프에서 사이클이 존재하면 코스가 순회 불가능, 사이클이 존재하지 않으면 코스가 순회가 가능하다고 판단해주면 된다.

visit set으로 방문점 파악, route set으로 사이클 존재 여부를 파악하게 하여 코드를 작성하였다. 방문점, 사이클 존재 파악시 in을 사용하면 시간복잡도가 O(N)이라 비효율적인 코드가 아닌가 하는 생각이 들 수 있다.

Python의 경우 list, tuple 자료형에서는 in 사용시 하나하나 순회하기 때문에 O(N)이지만, set이나 dictionary에서는 내부적으로 hash를 통해서 자료들을 저장하기 때문에 해시 충돌이 정말 많이 발생하지 않는 이상 O(1)로 작동한다.

소스 코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        route = set()
        visit = set()
        graph = collections.defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        
        def dfs(x):
            if x in route:
                return False
            if x in visit:
                return True
            
            visit.add(x)
            route.add(x)
            
            for arrive in graph[x]:
                if not dfs(arrive):
                    return False
            
            route.remove(x)
            return True
    
        for x in list(graph):
            if not dfs(x):
                return False

        return True