[파이썬 알고리즘 인터뷰] 39. 코스 스케줄

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

39. 코스 스케줄

leetcode 207. Course Schdule 문제입니다.

leetcode.com/problems/course-schedule/

 

 

풀이

 코스를 그래프로 만들고, 그래프가 순환 그래프인지 판단하는 풀이입니다.

def canFinish(self, numCourses,prerequisites):
    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

        # 이미 방문했던 노드이면
        if i in visited:
            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