210. Course Schedule II

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

Course Schedule II - LeetCode

Solution

class Solution:
    def __init__(self):
        self.ans = []
        self.graph = defaultdict(set)
        self.visit = None

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:        
        for i, j in prerequisites:
            self.graph[i].add(j)
        self.visit = [0] * numCourses

        for i in range(numCourses):
            if not self.dfs(i):
                return []
        return self.ans
    
    def dfs(self, i):
        if self.visit[i] == 1:
            return True
        elif self.visit[i] == -1:
            return False
        
        self.visit[i] = -1
        
        for k in self.graph[i]:
        	if not self.dfs(k):
        		return False
        
        self.visit[i] = 1
        self.ans.append(i)
        return True

• graph를 defaultdict(set)으로 선언한다.
• visit을 만들 때, [0,0...0]을 for문 돌리지 말고 위의 연산을 사용한다.
• 각 노드를 돌면서 하위 노드로 내려간다.
• 하위 노드를 내려가다가 이전에 지나쳤던 노드가 나오면 False를 반환한다.
• 가장 먼저 visit = 1이 되는 노드부터 수강하면 되므로, ans에 순서대로 추가한다.
• visit 1로 표시되면 그 아래로 다 괜찮다는 뜻이므로 더 검사하지 않는다.

defaultdict

from collections import defaultdict

 

사전에 없는 키를 찾거나 접근하면 에러가 발생한다.

defaultdict를 사용하면 없는 키라도 default로 설정한 타입의 value를 갖게 된다.

즉, 사전에 키가 있는지 검사하는 과정을 생략할 수 있다.

인자로는 int, list, set 등이 올 수 있다.

from collections import defaultdict

d = defaultdict(int)
print(d['0'])   # 0
print(d)        # {'0':0}