[LeetCode] 210. Course Schedule II

😎풀이

1. 해당 문제는 진입 차수가 결정되는 위상정렬 문제이다.
2. 그래프를 생성하여 key: 코스, value: 필요 코스로 Map을 구성한다.
3. 초기 진입을 위해 진입 차수가 0인(필요 코스가 존재하지 않는) 노드를 queue에 추가한다.
4. 위상 정렬을 수행하여 현재 코스에서 필요 코스를 순회하며 진입 차수가 0이 될 경우 queue에 추가해 순회한다.
5. 기록된 순서가 numCourse와 일치한다면 해당 배열을 반환하고, 완전히 수강할 수 없다면 빈 배열을 반환한다.

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const adjList: Map<number, number[]> = new Map();
    const inDegree: number[] = new Array(numCourses).fill(0);
    
    // 그래프 생성
    for (const [course, pre] of prerequisites) {
        if (!adjList.has(pre)) {
            adjList.set(pre, []);
        }
        adjList.get(pre)!.push(course);
        inDegree[course]++;
    }

    // 진입 차수가 0인 노드를 큐에 추가
    const queue: number[] = [];
    for (let i = 0; i < numCourses; i++) {
        if(inDegree[i] !== 0) continue
        queue.push(i);
    }

    // 위상 정렬 수행
    const order: number[] = [];
    while (queue.length) {
        const current = queue.shift()!;
        order.push(current);

        if (!adjList.has(current)) continue
        for (const neighbor of adjList.get(current)) {
            inDegree[neighbor]--;
            if(inDegree[neighbor] !== 0) continue
            queue.push(neighbor);
        }
    }

    // 모든 코스를 방문했는지 확인
    return order.length === numCourses ? order : [];
}