207. Course Schedule

Course Schedule

---

어떤 과목 A 가 주어질 때, 그 과목의 선수 과목 B가 존재하고 이를 [A, B] 라는 리스트로 표현합니다. 이처럼 과목과 그에 맞는 선수 과목의 리스트들이 존재할 때 주어진 목표는 해당 과목들을 모두 이수할 수 있는가? 에 관한 것입니다.

 

즉 [[A, B], [B, A]] 라고 문제에 주어진다면 A를 이수하기 위해선 먼저 B를 이수해야 하고 그 다음 값에선 B를 이수하기 위해선 A를 먼저 이수해야 합니다. 이럴 경우 A, B 둘 다 이수하지 못하므로 False 를 리턴하면 됩니다.

 

문제의 스토리는 이와 같은데 결국 해야 하는것은 방향성 그래프(Directed Graph) 에서 Cycle 을 찾는 문제입니다.

 

방향성 그래프에서 사이클을 찾는 방법은 DFS 와 BFS 가 있고 풀이할 때 쓰는 자료구조로는 Tri Color marking 과 Set 이 있습니다.

 

저는 DFS 와 Tri color marking 으로 풀이하였습니다. 

(https://youtu.be/rKQaZuoUR4M)

 

Tri color marking 은 말은 어렵지만 사실은 3가지 상태를 표현한다고 보면 됩니다. 즉 최초의 상태 White, 방문 중인 상태 Gray, 방문이 완료된 상태 Black 으로 말이지요.

 

만약 어떤 노드 A에서 다음 노드 B로 이동한다고 할 때 다음 노드 B가 방문 중인 상태 Gray 라면 어떤 의미일까요? 그건 바로 다른 어떤 노드 C에서 이미 노드 B를 방문중에 있다는 의미입니다. (DFS 로 풀이한다고 보면 이전에 지나온 노드라는 것이지요.) 이럴 경우 사이클이 생성된 것입니다. 

 

즉 이미 방문중인 노드 (Gray 인 상태) 에 다음에 방문해야할 노드가 있다면 사이클이란 의미입니다.

 

아래의 코드에서는 visited 란 딕셔너리를 두고 각 노드 의 상태 값을 넣어서 계산하였습니다. 1은 방문중이고 2는 방문이 완료되었음을 의미합니다.

class Solution:

    def dfs(self, node, graph, visited):

		# 더 이상 node 를 선수로 한 방문 노드가 없을 때
        if node not in graph:
            return True

        for n in graph[node]:
        	# 이미 방문 중인 노드라면
            # 해당 노드의 완료 여부를 리턴
            if n in visited:
                return visited[n] == 2
            # 노드를 방문 중인 상태로 변경
            visited[n] = 1
            if not self.dfs(n, graph, visited):
                return False
            # 노드를 완료로 변경
            visited[n] = 2

        return True

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)

        for p in prerequisites:
            graph[p[1]].append(p[0])

        visited = defaultdict(int)

        for node in graph:
            visited[node] = 1
            if not self.dfs(node, graph, visited):
                return False
            visited[node] = 2

        return True