[파이썬 알고리즘 인터뷰][그래프] 코스 스케줄

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

우선순위가 있는 task들에 대해 모든 코스가 완료 가능한지 판별

 

책에서 구현된 코드

# 재귀 - Fail
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):
        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

# Pruning 재귀
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):
        if i in traced:
            return False
        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

 

기억해야할 기법

• 싸이클 문제
  
  • 어떤 위치의 노드에서든 prerequisite을 따라가다보면 해결할 수 있는 노드가 나타나야함
  • 이 과정에서 싸이클이 생길 경우 다른 노드의 탐색 결과에 상관 없이 task를 완료할 수 없음
• dfs return 구조
  • 어떤 상황일 때 탐색이 이어가거나 종료되야하는지 명확하게 정하고 그 구조를 만들 수 있어야함
• defaultdict의 for문
  • for문에서 값이 변경될 수 있으므로 타 객체로 복사하여 사용

 

내가 구현한 코드

# Fail
from collections import defaultdict

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    needed = defaultdict(list)
    discovered = [False for _ in range(numCourses)]

    for then, prev in prerequisites:
        needed[then].append(prev)

    def dfs(elts: list, n: int):
        res = True

        if discovered[n]:
            return res
        if len(needed[n]) == 0:
            discovered[n] = True
            return res

        for t in needed[n]:
            if t in elts:
                return False
            res = res and dfs(elts+[n], t)

        discovered[n] = res
        return res

    for i in range(numCourses):
        dfs([], i)

    return False not in discovered

• 재귀에 대해 명확하게 phase를 나눌 것
• Pruning을 위한 구조를 설계할 것