[LeetCode] Course Schedule

그래프와 DFS, 위상정렬을 공부해볼 수 있는 아주 좋은 문제였다. 문제의 조건은 어떤 과목을 수강할 때 선수과목을 먼저 듣고 들어야한다. 주어진 강의 목록들을 모두 수강할 수 있다면 True를, 선수과목에 이상이 있어서 모두 수강할 수 없다면 False를 리턴하면 되는 문제이다.

 

접근방법은 우선 인접리스트 형태의 그래프를 만들고 깊이 우선 탐색을 하면서 위상정렬을 수행하는 것이다. 탐색 함수가 종료될 때마다 현재 위치를 기록하고, 탐색이 끝났다면 기록한 배열을 뒤집어주면 위상정렬이 수행된다. 위상정렬 배열을 보면서 수강목록들을 다시 보면서 이상이 있다면 False를 리턴하면 해결할 수 있다.

 

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        self.mark = []
        graph = [[] for i in range(numCourses)]
        visited = [False] * len(graph)
        
        for pre in prerequisites:
            graph[pre[0]].append(pre[1])
          
        for node in range(len(graph)):    
            if not visited[node]:
                self.dfs(node, visited, graph)        
        self.mark.reverse()
        
        for pre in prerequisites:
            start = self.mark.index(pre[0])
            end = self.mark.index(pre[1])
            if start >= end:
                return False
        
        return True
        
    def dfs(self, idx, visited, graph):
        if visited[idx]:
            return
        
        visited[idx] = True
        for node in graph[idx]:
            self.dfs(node, visited, graph)
        self.mark.append(idx)