[Graph][Medium] 207. Course Schedule

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

 

Q. 전체 코스의 수 numCourses와 해당 코스의 선학습 데이터 prerequisites 가 주어질 때, 전체 코스를 수강할 수 있는지 여부를 반환하라. 

 

Solution. 

  코스 및 경로 데이터를 우선, 노드 기반으로 정리한다. 

  특정 코스를 듣기 시작해서 추가 경로가 없는 마지막 코스노드까지 중복해서 방문하는 노드가 있으면, 사이클이 있는 것이므로, 수강 불가능 한 것이다. 

  이 과정을 각 시작 코스별로 수행 해 주며, 불가능한 코스가 하나라도 생긴다면, 전체 수강 불가능하다고 하겠다. 

 

  그래프 방문 + back track(방문 check) 비슷하게 접근하면 될 것 같다. 

  이때, 그래프 경로를 그대로 따라가야 하므로, DFS 탐색을 해야 한다. 

 

  이미 한번 판단한 경로는 다른 진입로로 들어와도 같은 결과를 갖는다. 

  따라서 캐싱 최적화를 할 때는 노드 기준으로 1회만 해 주면 되겠다. 

 

  위 논리로 코드를 작성해 본다. 

 

  

bool canFinish_help(vector<int>& vCache, vector<vector<int>>& vPath, vector<bool>& vVisit, int idx)
{
    if (vVisit[idx])
        return false;

    if(vCache[idx] >= 0)
        return vCache[idx]==1;

    vVisit[idx] = true;

    for (int q = 0; q < vPath[idx].size(); ++q)
    {
        int nextIdx = vPath[idx][q];
        if(!canFinish_help(vCache, vPath, vVisit, nextIdx))
        {
            vCache[idx] = 0;
            break;
        }
    }
    vVisit[idx] = false;
    vCache[idx] = vCache[idx]<0 ? 1 : vCache[idx];
    return vCache[idx]==1;
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
{
    vector<vector<int>> vPath(numCourses, vector<int>());
    for (int q = 0; q < prerequisites.size(); ++q)
        vPath[prerequisites[q][0]].push_back(prerequisites[q][1]);

    vector<int> vCache(numCourses, -1);
    for (int q = 0; q < prerequisites.size(); ++q)
    {        
        vector<bool> vVisit(numCourses, false);
        if (!canFinish_help(vCache, vPath, vVisit, prerequisites[q][0]))
            return false;
    }
    return true;
}

  

적절한 결과를 얻었다. 

 

 

Note ) 문제 해석이 중요하다. 

 영어가 문제인가 예제가 적은가, 둘다 아니라면 유형숙지가 필요한가. 

 튼, 그래프 문제의 주요 형태 중 하나.

 

 

Note 2) 3달 정도 뒤 다시 풀기 실패. 

 key 1. 한 과목순으로 들어가서 끝까지 확인하고 다시 나오고를 반복한다. -> DFS approach 필요. 

 key 2. 과목당 visit 체크가 필요하다. DFS를 쓰므로, backtrack 방식을 사용. 

 key 3. 과정 중, 체크가 끝난 과목은 다시 할 필요가 없다. - cache 필요.