207. Course Schedule

문제 링크:https://leetcode.com/problems/course-schedule/

강의의 선수과목이 있을 때, 전부 수강할 수 있는지 여부를 묻는 문제다.

Solution

Graph

선수 과목의 관계를 그래프로 나타낼 수 있다. 선수 과목이 없는 과목을 먼저 수강하여 선수과목이 있는 과목의 조건을 완화할 예정이므로 선수과목 -> 과목 형태의 그래프를 구성한다.

Algorithm

• 과목간의 선수 관계를 그래프로 표현한다. (선수과목 -> 과목)
• 각 과목의 선수과목 개수를 배열로 나타낸다 (과목idx -> 선수과목 개수)
• queue를 구성해 우선 선수과목 개수 배열을 탐색해 0 인 과목 즉 선수과목이 필요 없는 과목을 queue에 삽입한다.
• queue가 모두 제거될 때 까지 수강 가능한 과목을 듣고 order에 삽입, 해당 과목이 선수과목 중 하나인 과목의 선수과목 개수를 줄인다.
• 선수과목의 개수가 줄어든 경우 선수과목을 모두 수강했는지 확인해 queue에 삽입한다.
• 위 과정을 반복하면서 가능한 최대한 강의를 수강하고 order.length를 확인해 모든 과목을 들을 수 있는지 확인한다.

구현

var canFinish = function(numCourses, prerequisites) {
    const prereqMap = new Map();
    const order = [];
    const prereqLeft = Array(numCourses).fill(0);
    const queue = [];
    
    // 그래프 생성
    prerequisites.forEach(([course, reqCourse]) => {
        prereqMap.has(reqCourse) ? prereqMap.set(reqCourse, [...prereqMap.get(reqCourse), course]) : prereqMap.set(reqCourse, [course]);
        prereqLeft[course]++;
    });

    // 수강 가능한 과목 queue에 삽입
    prereqLeft.forEach((el, idx) => {
        if (el === 0) queue.push(idx);
    });
    
    // 수강 가능한 과목을 수강, 나머지 과목의 선수 조건 재설정
    while (queue.length) {
        const cur = queue.shift();
        order.push(cur);
        if (prereqMap.has(cur)) {
            prereqMap.get(cur).forEach((el) => {
                // 선수과목이였던 과목의 카운트를 줄이고 수강 가능할 경우 queue에 추가
                prereqLeft[el]--;
                if (prereqLeft[el] === 0) queue.push(el);
            });
        }
    }
    
    // 들은 과목 수가 전체 과목 수와 같은지 확인
    return order.length === numCourses;
};