[백준] 14567 - 선수과목

문제 링크
https://www.acmicpc.net/problem/14567

느낀 점

• 위상정렬의 가장 기본적인 문제 형태라고 생각된다.
• 진입차수를 따져주는 것이 위상정렬에서 키 포인트라고 생각되는데, 진입차수에 대한 배열을 만들고 진입차수가 0인 경우에만 다시 큐에 넣어서 순회해주어야 시간초과, 메모리 초과를 피할 수 있다!
• 입력에 대해 두 가지 자료구조를 생각해볼 수 있다. 아마 현재 문제에서는 입력 값의 길이가 500000이라서 vector<vector<int>>도 괜찮을 수 있지만, 입력 값의 길이가 더 커진다면, 아마 map으로 조회를 해야 시간 초과가 안 날 것 같다! 
  • map의 조회성능 : O(logN), 삽입, 삭제 성능: O(logN)
  • 인접리스트의 조회성능 : O(1), 삽입, 삭제 성능: O(N)

map<int, vector<int>> courses;
vector<vector<int>> courses;

#include <iostream>
#include <set>
#include <deque>
#include <map>
#include <vector>

using namespace std;

int main()
{
    // initialize
    int N, M, A, B;
    cin >> N >> M;
    vector<int> answer(N + 1, 0);
    vector<int> needPrerequisite(N + 1, 0);
    map<int, vector<int>> courses;
    deque<int> queue;
    for (size_t i = 0; i < M; i++)
    {
        cin >> A >> B;
        courses[A].push_back(B);
        needPrerequisite[B]++;
    }
    for (size_t i = 1; i <= N; i++)
    {
        if (needPrerequisite[i] == 0)
        {
            queue.push_back(i);
            answer[i] = 1;
        }
    }

    while (!queue.empty())
    {
        int qPop = queue.front();
        queue.pop_front();
        for (auto elem : courses[qPop])
        {
            answer[elem] = max(answer[qPop] + 1, answer[elem]);
            needPrerequisite[elem]--;
            if (needPrerequisite[elem] == 0)
            {
                queue.push_back(elem);
            }
        }
    }
    for (size_t i = 1; i <= N; i++)
    {
        if (i != N)
        {
            cout << answer[i] << " ";
        }
        else
        {
            cout << answer[i];
        }
    }
    return 0;
}