[알고리즘][그래프] - 8. 코스 스케줄

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/course-schedule/submissions/

0을 완료하기 위해서 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.

---

[DFS로 순환 구조 판별 - 시간 초과]

import collections


class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(list)

        for x, y in prerequisites:
            graph[x].append(y)

        trace = set()

        def DFS(i):
            #순환구조면 False
            if i in trace:
                return False

            trace.add(i)

            for y in graph[i]:
                #이미 방문했던 노드라면 False
                if not DFS(y):
                    return False
            #탐색 종료 후 순환 노드 삭제
            trace.remove(i)

            return True

        for x in list(graph):
            if not DFS(x):
                return False
        return True

• 시간초과가 뜬다. 
• 아래 가지치기를 이용한 최적화를 마친 코드를 이용해 풀어보자

[가지치기를 이용한 최적화]

import collections


class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(list)

        for x, y in prerequisites:
            graph[x].append(y)

        trace = set()
        visited = set()
        
        def DFS(i):
            #순환구조면 False
            if i in trace:
                return False
            #이미 방문한 노드라면 무조건 True를 돌려서 재탐색하지 않게 한다.
            if i in visited:
                return True
            
            trace.add(i)

            for y in graph[i]:
                #이미 방문했던 노드라면 False
                if not DFS(y):
                    return False
            
            #탐색 종료 후 방문 노드 추가
            visited.add(i)
            #탐색 종료 후 순환 노드 삭제
            trace.remove(i)

            return True

        for x in list(graph):
            if not DFS(x):
                return False
        return True

• 순환 구조가 아닌 경우에 순환구조로 오해를 할 수 있기 때문에 이를 막고자 trace.remove(i)와 같은 코드를 넣어 처리해주어야 한다.

[defaultdict 순회 문제]

graph를 list(graph)로 묶어준 이유는 defaultdict를 사용해서 키가 없는 딕셔너리에 대해서 빈 값 조회시 널(Null)오류가 발생하지 않게 처리해주었다. 이때 이 처리에 디폴트를 생성하는 구조로 만들어 graph 값이 변경된다는 오류가 발생하게 된다. 

이를 해결하기 위해서 list(graph)로 새로운 복사본을 생성해 해결해야 한다.