course schedule

Course Schedule

• prerequisite : [a,b] = a course를 완료하기 위해 b course를 먼저 완료 해야함
• numCourses : 코스 개수, prerequisites 가 주어졌을때 전부 완료가능하면 True 아니면 False

Solution1

• 각 course 를 node 로 prerequisite 를 edge 로 생각하면 directed graph로 표현가능
• directed graph에 cycle 이 존재하는 지 판별해서 존재하는 경우 False, 없으면 True
• dfs를 이용해 한 노드에서 출발하는 경로중에 cycle이 존재하는 지 검사할수 있음(has_cycle)
• 방문한 노드 기록(visitied)
• 해당 노드를 출발점으로 하는 어떤 경로에도 cycle이 없다고 결정(finished)
• visit했지만 finish는 아직 못한 노드가 존재 = cycle이 존재

Code1

from collections import defaultdict

class Solution(object):
    def canFinish(self, numCourses, prerequisites):

        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[a].append(b)

        visited = [False]*numCourses
        finished = [False]*numCourses

        def has_cycle(node):
            visited[node] = True
            for nxt in graph[node]:
                # 방문하지 않은 이웃 노드를 방문해서 cycle 검사
                if not visited[nxt] and has_cycle(nxt): return True

                # visited, not finished
                elif not finished[nxt]: return True 

            finished[node] = True
            return False

        # 결정되지 않은 node를 방문해서 cycle이 존재하면 False
        for node in list(graph.keys()):
            if not finished[node] and has_cycle(node): return False
        # 모든 출발가능 정점에서 cycle이 없는경우
        return True

Solution2

• traced : 한 출발점에서의 재귀적인 방문 기록
• finished : 해당 노드를 출발점으로 하는 어떤 경로에도 cycle이 없다고 결정

code2

from collections import defaultdict

class Solution(object):
    def canFinish(self, numCourses, prerequisites):

        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[a].append(b)

        traced = [False] * numCourses
        finished = [False] * numCourses

        def is_cycled(node):

            traced[node] = True
            for nxt in graph[node]:
                if traced[nxt]: return True
                elif not finished[nxt] and is_cycled(nxt): return True

            traced[node] = False
            finished[node] = True
            return False

        for node in list(graph.keys()):
            if not finished[node] and is_cycled(node): return False

        return True