[ leetcode 문제풀이 ] Course Schedule

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

Course Schedule - LeetCode

(Course Schedule 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Course Schedule 문제 설명 >

 

Course Schedule 문제는 다음과 같다.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

수강해야하는 numCourses개의 강좌가 0에서 numCourses - 1로 이름 붙여져 있다. prerequisites[i] = [ai, bi] : ai 강좌를 들으려 한다면 반드시 bi 강좌를 들어야 함을 나타내는 prerequisites 배열이 주어진다. (예시 생략)

너가 모든 강좌를 다 들을 수 있다면 true를 리턴하고, 그렇지 않으면 false를 리턴하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 1 ≤ numCourses ≤ 10^5,  0 ≤ prerequisites.length ≤ 5000,  prerequisites[i].length = 2, 

0 ≤ ai, bi < numCourses 과 prerequisites[i]은 서로 다른 순서쌍으로 이루어져 있다는 것이다.

 

 

 

---

< Course Schedule 문제 접근 >

 

vector나 2차원 vector로 강좌 간의 이수 관계를 나타내어보려 했으나 선이수 구조가 복잡해질 경우 이걸 하나하나 처리하기가 복잡해졌다. (↓실패한 코드, Cpp 사용)

 

#include <unordered_map>
#include <algorithm>
using namespace std;

void courseSearch(vector<vector<int>>& CourseGraph, int course, vector<int>& check){
    check[course] = 1;
    if(CourseGraph[course].empty()) return;
    while(!CourseGraph[course].empty()){
        courseSearch(CourseGraph, CourseGraph[course][0], check);
        CourseGraph[course].erase(CourseGraph[course].begin());
    }
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    unordered_map<int, bool> baseCase;
    for(int i=0;i<numCourses;i++)
        baseCase[i] = true;
        
    vector<vector<int>> CourseGraph(numCourses);
    for(vector<int> constraint : prerequisites){
        auto course = baseCase.find(constraint[1]);
        if(course != baseCase.end())
            baseCase.erase(course);
            
        auto checkpair = find(CourseGraph[constraint[1]].begin(), CourseGraph[constraint[1]].end(), constraint[0]);
        if(checkpair != CourseGraph[constraint[1]].end())
            CourseGraph[constraint[1]].erase(checkpair);
        CourseGraph[constraint[0]].push_back(constraint[1]);
    }
        
    vector<int> check(numCourses, 0);
    for(auto course : baseCase)
        courseSearch(CourseGraph, course.first, check);
        
    for(int i=0;i<numCourses;i++)
        if(!check[i]) return false;
    return true;
}

 

후이수강좌만을 CourseGraph에 저장해서 courseSearch를 해보면 될 것이라 생각했는데 선이수구조가 복잡한 경우(두 강좌 이상이 선이수강좌가 되는 경우) 탐색 및 선이수 처리를 이상하게 하며 오답을 출력하는 문제가 있었다.

 

그래서 정석적인 graph로 강좌 간 이수 관계를 나타내고자 하였다. 먼저 코드를 보면 다음과 같다. (Cpp 사용)

 

#include <algorithm>
using namespace std;

struct CourseNode{
    bool learned = false;
    vector<CourseNode*> parentNodes;
    vector<CourseNode*> childNodes;
}; // course 정보를 저장: 수강 여부, 선이수강좌, 후이수강좌
    
void courseSearch(CourseNode* Node){
    if(!Node->parentNodes.empty()) return; // 선이수강좌를 모두 들은 경우, 선이수강좌가 없는 경우
    Node->learned = true; // 수강 완료
    if(Node->childNodes.empty()) return; // 후이수강좌가 없는 경우 리턴
    for(CourseNode* childNode : Node->childNodes) // 후이수강좌에 대해 선이수 완료를 적용
        childNode->parentNodes.erase(find(childNode->parentNodes.begin(), childNode->parentNodes.end(), Node));
    while(!Node->childNodes.empty()){ // 후이수강좌에 대해 courseSearch 반복
        courseSearch(Node->childNodes.back());
        Node->childNodes.pop_back();
    }
}    
    
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    CourseNode* CourseGraph = new struct CourseNode[numCourses]; // 직접 메모리 할당 필요
    for(vector<int> constraint : prerequisites){ // CourseGraph 작성
        (CourseGraph+constraint[0])->parentNodes.push_back(CourseGraph+constraint[1]);
        (CourseGraph+constraint[1])->childNodes.push_back(CourseGraph+constraint[0]);
    }
        
    for(int i=0;i<numCourses;i++)
        courseSearch(CourseGraph+i); // 수강가능 여부 탐색
        
    for(int i=0;i<numCourses;i++)
        if(!CourseGraph[i].learned) return false;
    return true;
}

 

CourseGraph를 나타내기 위해 CourseNode를 정의했다. course의 수강여부, 남은 선이수강좌, 남은 후이수강좌를 저장한다. 이 CourseNode의 집합이 CourseGraph이다. 

courseSearch라는 함수를 통해 수강 여부 업데이트(by bool learned), 선이수완료 확인(if !Node→parentNodes.empty()), 후이수강좌에 대한 탐색의 재귀, 탐색의 종료(선이수 완료x, 후이수강좌x)를 구현하였다.

이렇게 모든 CourseNode에 대해 수강 가능 여부를 탐색한 후 하나라도 수강완료하지 못한 강좌가 있을 경우 false를 리턴하게 된다. 모두 수강 완료하였다면 true를 리턴한다.

 

Runtime: 32 ms(faster than 43.62%), Memory Usage: 15.5 MB(less than 14.59%)