[LeetCode][Topological Sort] Course Schedule 풀어보기

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

Course Schedule - LeetCode

 

문제는 위상정렬의 가장 간단한 형태의 문제입니다.

위상정렬 문제 자체는 어렵게 나오기 보다는 해당 문제가 위상정렬 문제임을 알아내는 것이 중요하다고 생각합니다.

 

보면 prerequisites의 [0]을 하기 위해서는 항상 이전에 [1]을 실행했어야하는데, 이것은 특정 순서를 지켜야하는 위상정렬에 적합합니다.

 

따라서 이를 판별하기 위해 그래프를 만들고 순환하지 않는지 체크했습니다.

class Node
{
public:
    Node(int n) : num(n), degree(0)
    {

    }
public:
    int num;
    int degree;
    vector<Node*> nexts;
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for (int i = 0; i < numCourses; ++i)
        {
            Node* pNode = new Node(i);
            pNodeMap.insert({ i, pNode });
        }

        for (auto pr : prerequisites)
        {
            // [0]을 하기 위해서는 [1]을 수행해야함
            // = [1] -> [0]
            pNodeMap[pr[1]]->nexts.push_back(pNodeMap[pr[0]]);
            ++pNodeMap[pr[0]]->degree;
        }

        queue<Node*> q;
        for (auto& [num, pNode] : pNodeMap)
        {
            if (pNode->degree == 0)
                q.push(pNode);
        }

        int count = 0;

        while (!q.empty())
        {
            Node* poll = q.front();
            q.pop();

            ++count;

            for (Node* next : poll->nexts)
            {
                --next->degree;

                if (next->degree == 0)
                {
                    q.push(next);
                }
            }
        }

        return count == numCourses;
    }

public:
    unordered_map<int, Node*> pNodeMap;
};

방법 자체는 투박하게 Linked List를 만들고 각각에 맞게 이은 후 

 

Kahn 알고리즘에 따라 차수를 빼다보면 답이 나옵니다.

 

다만 해당 코드의 성능은 별로였습니다.

---

개선코드입니다.

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int edgeCount = prerequisites.size();

        vector<int> indegree(numCourses, 0);

        // 인접 리스트를 연속 배열 형태로 구성
        vector<int> head(numCourses, -1);
        vector<int> to(edgeCount);
        vector<int> next(edgeCount);

        for (int i = 0; i < edgeCount; ++i)
        {
            int course = prerequisites[i][0];
            int prev = prerequisites[i][1];

            // prev -> course
            to[i] = course;
            next[i] = head[prev];
            head[prev] = i;

            ++indegree[course];
        }

        // queue 대신 고정 크기 vector 사용
        vector<int> q(numCourses);

        int front = 0;
        int back = 0;

        for (int i = 0; i < numCourses; ++i)
        {
            if (indegree[i] == 0)
            {
                q[back++] = i;
            }
        }

        int count = 0;

        while (front < back)
        {
            int cur = q[front++];
            ++count;

            for (int edge = head[cur];
                 edge != -1;
                 edge = next[edge])
            {
                int nextCourse = to[edge];

                if (--indegree[nextCourse] == 0)
                {
                    q[back++] = nextCourse;
                }
            }
        }

        return count == numCourses;
    }
};

연결 리스트와 queue의 활용을, vector로 치환해서 구현했기 때문에 성능이 좋아졌습니다.

물론 PS의 관점에서 좋아진거라고 봅니다.