[Leetcode/파이썬] 207. Course Schedule

Course Schedule

---

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

 

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]     # graph[i] : 과목 i를 선수과목으로 가지는 다음 과목들
        indegree = [0] * numCourses                 # indegree[i] : 과목 i의 진입 차수, 즉 선수과목 개수

        for to, fr in prerequisites :
            graph[fr].append(to)            # fr -> to 간선 추가
            indegree[to] += 1               # to 과목의 선수과목 수 (진입 차수) 1 증가

        q = deque()

        for i in range(numCourses) :        
            if indegree[i] == 0 :           # 선수과목이 하나도 없으면 지금 바로 수강 가능
                q.append(i)                 # 수강 가능하므로 큐에 추가
    
        taken = 0                           # 위상 정렬로 처리 완료한 과목 수(수업 몇개 들었니?)

        while q :                           # 현재 바로 들을 수 있는 수업을 들어보자.
            cur = q.popleft()               # 지금 수강 가능한 과목 하나 꺼내 처리 시작
            taken += 1                      # 해당 과목 처리 완료

            for nxt in graph[cur] :         # cur를 선수과목으로 가지는 후속 과목들
                indegree[nxt] -= 1          # nxt 입장에서 필요한 선수과목 하나가 충족됨
                if indegree[nxt] == 0 :     # nxt 수업을 듣기 위한 선수과목이 모두 충족되면
                    q.append(nxt)           # 수강 가능하므로 큐에 추가

        return taken == numCourses          # 모든 과목을 처리했으면 True, 아니면 False

class Vertex :
    def __init__(self, x) :
        self.x = x
        self.incoming = []
        self.outgoing = []

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

        for to, fr in prerequisites :
            if fr not in vertexes.keys() :
                vertexes[fr] = Vertex(fr)
            if to not in vertexes.keys() :
                vertexes[to] = Vertex(to)

            vertexes[fr].outgoing.append(to)
            vertexes[to].incoming.append(fr)

        q = deque()

        for vertex in list(vertexes.values()) :
            if len(vertex.incoming) == 0 :
                q.append(vertex)

        while q :
            vertex = q.popleft()
            cur = vertex.x

            for nxt in vertex.outgoing :
                vertexes[nxt].incoming.remove(cur)

                if len(vertexes[nxt].incoming) == 0:
                    q.append(vertexes[nxt])

            del vertexes[cur]

        return len(vertexes.values()) == 0

이 문제도 예전에 풀었던 문제인데 쉽게 풀리지 않아서 많은 것들을 참고 했다. 특히 코데풀님꺼 참고 하면서 클래스에 대해서 많이 공부할 수 있는 기회가 되었다. 

상세한 사항은 주석에 달아놨으니 참고 바람.