[1스4코2파] # 234. LeetCode 210. Course Schedule II

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (234차)
[4코1파] 2023.01.13~ (226일차)
[1스4코1파] 2023.04.12~ (137일차)
[1스4코2파] 2023.05.03 ~ (115일차)

Today :

2023.08.25 [234일차]
210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/

210. Course Schedule II

문제 설명

수강해야 하는 총 numCourses 강좌가 있으며 0부터
numCourses - 1 까지의 label로 지정되어 있음.
prerequisites[i] = [ai, bi]는 ai를 수강하기 위해서는 bi를 수강해야 하는데,
[0, 1] 쌍은 코스 0을 수강하려면 먼저 코스 1을 수강해야 한다는 것
모든 강좌를 마치기 위해 수강해야 하는 강좌의 순서를 return 하고, 모든 강좌를 마치기 위한 방법이 없으면 빈 배열을 return, 유효한 답변이 많으면 그 중 하나를 return 한다.

문제 풀이 방법

Topological Sort(위상 정렬) 을 사용해서 dfs로 탐색하여 푸는 문제~! 해당 문제의 시간 복잡도는 O(Edge+Node), O(p+n) 이게 되겠다~

내 코드

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        preMap = { c:[] for c in range(numCourses)}
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

        output = []
        visited, cycle = set(), set()
        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visited:
                return True

            cycle.add(crs)
            for pre in preMap[crs]:
                if dfs(pre) == False:
                    return False
                
            cycle.remove(crs)
            visited.add(crs)
            output.append(crs)
            return True

        for c in range(numCourses):
            if dfs(c) == False:
                return []
        return output        

증빙

여담

dfs 끝