[LeetCode/Python] 207. 코스 스케줄(Course Schedule)

0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다.

 

코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.

 

Example:

 

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

 

Output: true

 

 

 

** 깔끔한 풀이 **

 

1. DFS로 순환 구조 판별

 

 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        # 그래프 구성
        for x,y in prerequisites:
            graph[x].append(y)
 
        traced = set()
 
        def dfs(i):
            # 순환 구조이면 False
            if i in traced:
                return False
 
            traced.add(i)
            for y in graph[i]:
                if not dfs(y):
                    return False
            # 탐색 종료 후 순환 노드 삭제
            traced.remove(i)
 
            return True
 
        # 순환 구조 판별
        for x in list(graph):
            if not dfs(x):
                return False
 
        return True

 

순환 구조라면 False를 출력해야 하므로

 

집합 자료형을 이용하여 같은 곳을 반복한다면 False를 출력할 수 있도록 한다.

 

그리고 중요한 점은

 

해당 노드를 이용한 모든 탐색이 끝나게 된다면

 

traced.remove(i)를 이용하여 방문 내역을 삭제해야 한다.

 

그렇지 않으면 형제 노드가 방문한 기록이 남아서 순환이 아닌데 순환이라 잘못 판단될 수 있다.

 

 

 

 

2. 가지치기를 이용한 최적화

 

 

import collections
import heapq
import sys
 
 
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        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
            # 이미 방문했던 노드이면 True
            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
 

 

해설:

 

이미 방문했던 노드는 순환 구조가 아니라고 인증 마크를 받은 곳이니까

 

굳이 다시 갈 필요가 없다.

 

따라서 집합 자료형 변수 visited를 만들어서

 

탐색을 종료할 때 방문한 노드를 추가해준다.

 

이렇게 했을 경우

 

1번 코드 대비 10배 정도의 효율을 보인다..!