[ leetcode ] 207. Course Schedule

이 문제는 주어진 numCourses만큼의 과목들을 모두 수강할 수 있는 지를 판단하는 문제입니다.

numCourses가 주어진다면 과목은 0부터 numCourses-1까지 존재하며, prerequisites가 주어지는데 크기가 2인 배열의

집합으로 구성되어 있으며 [1,0]으로 표현되는 prerequisite은 1과목을 수강하기 위해서는 0과목을 먼저 수강해야 한다는 의미입니다.

 

문제를 분석해보면, [1,0], [0,1]처럼 cycle이 생기는 경우를 판단하는 문제이고 cycle이 생기지 않는다면 true를 반환합니다.

cycle이 생기는 것을 판단하기 위해서는 우선, 각 과목과 선수 과목이 있으면 해당 과목들을 표기하는 adjacent vector가 필요하고, 미리 들어야 하는 과목에 해당하는 것의 차수를 counting하여 BFS방식으로 해결할 수 있습니다.

 

1. 먼저 선수 과목 조건을 순회하면서 과목과 선수과목을 연결하고, 선수과목에 해당하는 과목은 count를 올려주며 해당 과목의 count가 0이되면 cycle이 없다는 의미이므로 두 가지 자료구조를 준비합니다.

2. count가 0인 과목들을 queue에 먼저 넣고, 하나씩 빼면서 뺀 해당 과목의 선수과목을 순회하며 count를 1씩  낮추고 0이면 queue에 넣는 방식으로 진행합니다.

3. 그렇게 되어서 queue에서 뺀 과목들을 answer vector에 하나씩 넣고, 마지막에 전체 answer vector크기와 numCourses를 비교하여 같으면 cycle이 없고 모두 수강할 수 있음을 의미합니다.

 

#include <vector>
#include <queue>

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> course;
        vector<int> adjacent[numCourses];
        vector<int> indegree(numCourses, 0);

        for (auto prerequisite : prerequisites) {
            adjacent[prerequisite[0]].push_back(prerequisite[1]);
            indegree[prerequisite[1]]++;
        }

        queue<int> non_prerequisites_course;
        for (int i = 0; i < numCourses; i++) {
            if (!indegree[i]) non_prerequisites_course.push(i);
        }

        while (!non_prerequisites_course.empty()) {
            int taken_course = non_prerequisites_course.front();
            course.push_back(taken_course);
            non_prerequisites_course.pop();

            for (auto adj : adjacent[taken_course]) {
                indegree[adj]--;
                if (!indegree[adj]) non_prerequisites_course.push(adj);
            }
        }
        return course.size() == numCourses;
    }
};

비슷한 문제로 cycle을 만들지 않는 node를 찾는 문제: https://leetcode.com/problems/course-schedule/