[알고리즘] 코스 스케줄

코스 스케줄

책 풀이

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = collections.defaultdict(list)
    for x, y in prerequisites:
        graph[x].append(y)

    traced = set()

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

        traced.add(i)
        for y in graph[i]:
            if not dfs(y):
                return False

        traced.remove(i)
        return True

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

    return True

# print(canFinish(2, [[1,0]]))
print(canFinish(2, [[0,1], [0,2], [1,2]])

각 코스 별로 순환하는 사이클이 없는지 검사하는 것이다. 하지만 이렇게 풀면, 만약 순환이 아니더라도 복잡하게 서로 호출하는 구조로 그래프가 구성되어 있다면, 불필요하게 동일한 그래프를 여러 번 탐색하게 될 수도 있다. 따라서 한 번 방문했던 그래프느느 두 번 이상 방문하지 않도록 무조건 True로 리턴하는 구조로 개선한다면, 탐색 시간을 획기적으로 줄일 수 있을 것이다.

    graph = collections.defaultdict(list)
    for x, y in prerequisites:
        graph[x].append(y)

    traced = set()
    visited = set()

    def dfs(i):
        # 순환 구조이면 False
        if i in traced:
            return False
        # 이미 방문했던 노드이면 True
        if i in visited: # 만약 순환 노드였으면 진작 걸러졌을 것이다. 남아 있는 것은 순환이 아닌 노드이므로 True
            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):
        if not dfs(x):
            return False
    
    return True

참고 문제 백준 텀프로젝트