[4코3파] #305. Leetcode graph (2)

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (305일차)
[4코1파] 2023.01.13~ (297일차)
[4코3파] 2023.10.01 ~ (35일차)

Today :

2023.11.04 [305일차]

Leetcode Graphc(2)

[9] 210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

문제 설명

수강신청 시, 어떤 강의를 수강하기 위한 선수 강의들의 순서를 정하는 문제이다.
강의들과 선수 강의들의 목록이 주어지는데, 각 강의는 순서가 정해진 선수 강의를 수강해야 한다. 모든 강의를 수강할 수 있는 순서를 반환한다.

문제 풀이 방법

그래프 자료구조와 위상 정렬(Topological Sort) 알고리즘을 사용한다.
dfs로 그래프를 탐색하는데, 각 과목을 노드로 나타내고, 선수 과목을 방향 간선으로 연결하는 그래프 자료 구조를 구성한다.
방문한 노드를 추적하기 위한 배열을 초기화한 후,
모든 노드에 대해서 아직 방문하지 않은 노드를 찾고,해당 노드를 시작으로 DFS를 수행한다.
이 때, DFS를 수행하면서 과목을 순서대로 나열한다음 DFS를 마친 노드를 방문한 노드로 표시하고, DFS를 수행한 결과로 얻은 과목 순서를 뒤집어서 반환한다.

내 코드

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      
            

---

여담