[코딩 테스트] 리트코드207 -Course Schedule (Medium) in Python

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false

 

총 들어야 하는 수업의 갯수  numCourses와 선수과목 정보 prerequistes 배열이 주어질 때,

모든 수업을 들을 수 있으면 True를, 아니면 False를 반환하세요.

 

prerequisites 배열의 원소 [a, b]는 a를 듣기 위해선 b를 들어야 함을 의미합니다.

 

예시:

 

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

 

풀이

예시로, numCourses = 5와 prerequisites = [[1, 4], [2, 4], [3, 1], [3, 2]]의 경우를 보자!

1을 듣기 위해선 4를, 3을 듣기 위해선 1, 2를, 2를 듣기 위해선 4를 먼저 들어야 함!

이 때, 아무 선수 과목이 필요 없는 5번과 4번을 먼저 듣고, 1번과 2번을 듣고, 3번을 들으면 되기 때문에 답은 True다.

 

만약 문제가 2번 수업을 들어야 4번 수업을 들을 수 있다 - 라는 조건이 추가된 채로 나왔다면, 4번에서 시작한 '사이클'이 생성되기 때문에 False가 될 것이다.

 

따라서 이 문제는,

임의의 노드에서 시작해 깊이 우선 탐색을 시작하되, 사이클이 생성되어 시작 노드로 다시 돌아오면 False가 되는 문제이다.

 

 

파이썬 풀이

 

class Solution:
	def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    	# 선수과목 관련 ref 테이블 먼저 만들어 줌
        # ref[i]는 i를 듣기 위해 먼저 들어야 하는
        # 과목들의 집합임!
        ref = [[] for _ in range(numCourses)]
        for x, y in prerequisites:
            ref[x].append(y)
        
        visited = [0] * numCourses
        
        # 각 노드 돌며 사이클 생성 확인
        for i in range(numCourses):
            if not self.dfs(ref, visited, i): #사이클생성
            	return False
        return True
        
    # 깊이우선탐색 함수
    def dfs(self, ref, visited, i):
    	# -1: 방문 중인 노드
        # 1: 이미 방문한 노드
        if visited[i] == 1:
            return True
        elif visited[i] == -1:
            return False
            
        visited[i] = -1 #방문 중
        
        for j in ref[i]:
            if not self.dfs(ref, visited, j):
                return False
        visited[i] = 1
        return True