[LeetCode] #207. Course Schedule (python)

문제

https://leetcode.com/problems/course-schedule/

Course Schedule - LeetCode

[a, b] 형식으로 구성된 a를 끝내려면 b를 먼저 끝내야 된다는 코스 리스트가 있다. 코스 개수 n도 함께 입력 받는다.

주어진 모든 코스를 완료 가능하다면 True를 반환하고 그렇지 않으면 False를 반환해야 한다.

 

예시 입출력

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

 

풀이

 

책 풀이

 

가지치기를 이용한 최적화

import collections

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

이 문제는 그래프가 순환 구조인지를 판별하는 방식으로 풀면 된다. 순환구조라면 해당 코스를 완료할 수 없기 때문에 순환구조가 아니어야 한다.

prerequisites를 그래프로 표현하기 위해 첫번째 값은 x, 두번째 값은 y로 풀어서 표현한다. 이때 y는 복수개로 구성이 가능하다. x : [y1, y2] 이런 형식이 된다. defaultdict(list)를 했기 때문에 복수개의 값으로 구성할 수 있다.

한번 방문했던 노드는 visited에 추가하고 만약 방문했던 노드라면 바로 True를 리턴한다.

traced는 탐색 과정에서 탐색한 노드를 추가하는 변수다. 탐색하다가 traced에 있는 노드면 순환구조이기 때문에 False를 return 한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰