210. Course Schedule II

Course Schedule II - LeetCode

 

이전에 풀었던 문제와 비슷하지만 이번에는 가능한 수강 순서 중 하나를 반환하는 문제다.

 

 

1. 위상 정렬

from typing import *
from collections import defaultdict, deque


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        if not prerequisites:
            return [i for i in range(numCourses)]

        graph = defaultdict(set)
        degree = [0] * numCourses

        for i in range(numCourses):
            graph[i] = set()

        for item in prerequisites:
            dsc, src = item
            graph[src].add(dsc)
            degree[dsc] += 1

        q = deque([])
        answer = []
        for i in range(len(degree)):
            if degree[i] == 0:
                q.append(i)

        while q:
            cur = q.popleft()
            answer.append(cur)
            for adj in graph[cur]:
                degree[adj] -= 1
                if degree[adj] == 0:
                    q.append(adj)

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

유무 판단이 아니라 경로를 추적하는 것이면 DFS가 아니라 위상 정렬이 좀 더 익숙해서 사용해보았다.

 

몇 가지 예외 처리가 필요한데

1. 만일 prerequisites(선수 조건)이 없다면 0 ~ numCourses-1의 정수가 각각 한 개씩 들어있는 list를 반환하면 된다. 첫 번째 라인에 처리해줬다.
2. 위상 정렬이 끝나고 방문순서 배열의 길이가 numCourses와 다르다는 것은 사이클이 존재해서 모든 노드를 위상을 구분하면서 탐색할 수 없다는 것이기 때문에 가능한 경우가 존재하지 않는다. 이런 경우는 마지막 라인에 빈 list를 반환하는 것으로 처리해줬다.