[LeetCode 207][Medium][Python] Course Schedule 상세 풀이 (feat. 순환 구조 판별)

Problem

 

1. 문제 접근

1-1. 문제 해석

본 문제는 주어진 노드간 인과관계를 통하여 순환 구조가 존재하는지에 대한 여부를 확인하는 문제이다. 순환 구조가 존재한다면 모든 Course를 수강할  수 없을 것이며, 반대로 존재하지 않는다면 모든 Course는 수강할 수 있을 것이다.

 

1-2. 자료 그래프화

노드간 인과관계를 나타내기 위해 prerequisites 변수들에 대하여 그래프로 표현해보자. 여기서 파이썬에서 제공하는 defaultdict 모듈을 이용하여 쉽게 구현할 수 있다.

# defaultdict(<class 'list'>, {0: [1, 2], 1: [3, 4], 3: [4], 4: [], 2: []})

# 자료 Graph화
preMap = collections.defaultdict(list)
for course, prereq in prerequisites:
    preMap[course].append(prereq)

 

1-3. DFS 방식을 통한 탐색

고려사항 1.

중복 반복 판단 여부만 된다면 순환 구조 판별할 수 있다. 방문한 노드를 저장할 수 있는 자료구조를 생성하여 구현한다.

 

고려사항 2.

실제로는 순환 구조가 아닌데, 방문 기록에 남아있다는 관계로, 순환 구조로 판별할 수 있는 경우가 존재한다. 그렇기에, 방문한 내역은 반드시 삭제가 필요하다.

 

2. 문제 답안

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        # 자료 Graph화
        preMap = collections.defaultdict(list)
        for course, prereq in prerequisites:
            preMap[course].append(prereq)

        #순환구조 판단을 위한 방문 자료구조
        visited = set()

        def dfs(course):

            # 중복 반복시 순환구조 판단 False 리턴
            if course in visited:
                return False

            # 순환 구조가 아닐 시 끝점에서는 empty List 존재, True 반환
            if preMap[course] == []:
                return True
            
            # 방문내역 추가
            visited.add(course)

            # Graph 노드 탐색, dfs(node) 반환값이 False 일시 False 반환
            for prereq in preMap[course]:
                if not dfs(prereq): return False
        
            visited.remove(course) # 순환구조 오판 가능성 고려
            preMap[course] = [] # 중복방문 없애기 위한 최적화

            return True


        for course in range(numCourses):
            if not dfs(course): return False
        
        return True