[Leetcode] 210. Course Schedule II - JS

https://leetcode.com/problems/course-schedule-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
수강해야 하는 총 numCourses 강좌가 있으며 0부터 numCourses - 1까지 레이블이 지정됩니다. 
prerequisites[i] = [ai, bi]는 수강하려는 경우 먼저 bi 강좌를 수강해야 함을 나타내는 배열 전제 조건이 제공됩니다.

예를 들어, [0, 1] 쌍은 코스 0을 수강하려면 먼저 코스 1을 수강해야 함을 나타냅니다.
모든 강좌를 마치기 위해 수강해야 하는 강좌의 순서를 반환합니다. 
유효한 답변이 많으면 그 중 하나를 반환하십시오. 모든 과정을 완료하는 것이 불가능할 경우 빈 배열을 반환합니다.

제한조건
--------------------
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- ai != bi
- 모든 [ai, bi] 쌍은 서로 다르다.

 

2. 접근 방법

접근방법
--------------------
Course Schedule 문제와 비슷하게 접근했다.
본 문제에서는 순환일 경우는 빈 배열, 순환이 아닐 경우 수강 순서까지 담은 배열을 반환해야한다.

기존 로직에 추가로 courseOrder 배열을 선언하여 방문이 완료된 강좌를 courseOrder에 추가한다.

 

 

3. 코드

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
    const graph = Array.from({length:numCourses}, () => []);

    for (let [course, pre] of prerequisites) {
        graph[course].push(pre);
    }

    const visited = Array.from({length:numCourses}, () => 0);
    const courseOrder = [];

    function hasCycle(course) {
        if (visited[course] === 1) return true;
        if (visited[course] === 2) return false;

        visited[course] = 1;

        for (let pre of graph[course]) {
            if (hasCycle(pre)) return true;
        }

        visited[course] = 2
        courseOrder.push(course);

        return false;
    }

    for (let course = 0; course < numCourses; course++) {
        if (hasCycle(course)) return [];
    }

    return courseOrder;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(V + E)

- 공간복잡도: O(V + E)

 

[Leetcode] Course Schedule - JS 문제를 이해를 한 상태로 접근하니 간단하게 해결할 수 있었다.

수강과목에 대한 선행과목을 인접 리스트로 구현하고

visited 배열에 수강과목과 선행과목들을 재귀함수로 탐색하여 순환이 존재하는지 파악했다.

 

순환이 존재하지 않은체로 방문이 완료되면 courseOrder에 현재 강좌를 추가하여 수강 순서를 저장한다.

 

모든 과목을 순회하면서 순환 여부를 판단하여 순환이 된다면 빈 배열, 그렇지 않다면 courseOrder를 반환하였다.