[LeetCode] 210 | Course Schedule II | Python

---

문제 링크: https://leetcode.com/problems/course-schedule-ii/

---

문제

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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

---

조건

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

---

내 풀이

Topology sort를 사용하면 된다.

주어진 종속관계를 배열(pre)로 정리하고, 선수강이 필요한 수를 다른 배열(nums)에 저장한다.

선수강이 필요하지 않은 것들을 큐(q)에 넣어둔다.

* 선수강이 필요하지 않은 것들은 바로 정답배열에 넣을 수 있다.

그렇기때문에 큐(q)에서 하나(temp)씩 빼서(먼저 이 과목을 들었다는 뜻) 정답배열(ans)에 추가하고, temp를 들었으므로, temp가 선수강으로 필요했던 다른 과목들의 수를 nums에서 하나씩 제거한다.

다시 *로 돌아가서 이를 반복한다.

---

코드

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        pre = [[] for _ in range(numCourses)]
        nums = [0 for _ in range(numCourses)]
        ans, q = [], []
        
        for prerequisite in prerequisites:
            pre[prerequisite[1]].append(prerequisite[0])
            nums[prerequisite[0]] += 1
        
        for n in range(numCourses):
            if nums[n] == 0:
                q.append(n)
                
        while q:
            temp = q.pop()
            ans.append(temp)
            for req in pre[temp]:
                nums[req] -= 1
                if nums[req] == 0:
                    q.append(req)

        if len(ans) == numCourses:
            return ans
        else:
            return []