207. Course Schedule

leetcode.com/problems/course-schedule/

Course Schedule - LeetCode

import collections

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        indegrees = [0]*numCourses
        graph = defaultdict(list)
        
        for u, v in prerequisites :
            indegrees[v] += 1
            graph[u].append(v)

        q = deque([])
        
        for i in range(len(indegrees)) :
            if indegrees[i] == 0 :
                q.append(i)
                
        finished = 0
        
        while q :
            
            curr = q.popleft()
            finished += 1
            
            for i in graph[curr] :
                indegrees[i] -= 1
                if indegrees[i] == 0 :
                    q.append(i)
                    
        return finished == numCourses
    

 

정리 :

순서가 있는 문제는 위상정렬 사용.

recursive보다는 iterative로 접근.