Leetcode: Course Schedule II

There are a total of n courses you have to take labelled from 0 to n - 1.

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, 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.

 

Example 1:

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

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

 

수업의 총 개수와, 각 수업을 듣기 위해 먼저 들어야 할 수업들의 리스트가 주어졌을 때에 순서에 맞게 모든 과목을 듣는 방법을 구한 문제이다. 위상정렬로 풀 수 있는 대표적인 문제이다.

 

위상정렬은 incoming edge가 없는 node를 하나씩 result에 더해가고, 노드가 추가될때마다 이 노드의 outgoing edge를 제거하는 식으로 해결한다. 이를 위해 최초에 prerequisites를 순회하며 각 노드의 incoming edge count와 outgoing edge들을 기록해둔다.

특정 시점에 어떤 노드에 incoming edge가 있다는 것은, 해당 노드 이전에 먼저 있어야 할 노드가 아직 나타나지 않았다는 의미이므로, 해당 노드가 사용되어서는 안된다. 반대로, 특정 시점에 어떤 노드의 incoming edge가 없다는 것은, 해당 노드는 언제든 result에 다음 순서에 추가될 수 있다는 의미이다. 이것이 이렇게 incoming edge가 없는 노드들을 먼저 result에 append 하고, 그 때마다 이 노드를 prerequisite으로 가지는 노드와의 edge incoming edge를 제거하고, 다시 incoming edge가 없는 노드들을 찾는 식으로 반복한다. 반복은 queue를 이용한다. Reference에 설명이 잘 되어있는 블로그 링크를 추가해두었다.

결과적으로 queue에 더 이상 원소가 없을때 (= incoming edge가 없는 노드가 없을 때), 현재까지 정렬된 노드들의 갯수가 주어진 노드의 총 갯수와 동일하다면 정렬이 완료된 것이고, 그렇지 않다면 위상정렬이 될 수 없는 노드가 있다 = prerequisite의 cycle이 존재한다라는 의미이므로 empty list를 리턴한다.

 

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        incomings, outgoings = [0 for _ in range(numCourses)], [[] for _ in range(numCourses)]
        for course, pre_course in prerequisites:
            incomings[course] += 1
            outgoings[pre_course].append(course)

        queue = []
        for idx, incomings_count in enumerate(incomings):
            if incomings_count == 0:
                queue.append(idx)

        result = []
        while queue:
            course = queue.pop()
            result.append(course)
            for next in outgoings[course]:
                incomings[next] -= 1
                if incomings[next] == 0:
                    queue.append(next)

        return result if len(result) == numCourses else []

 

 

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

Course Schedule II - LeetCode

 

Reference

• m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)