백준 14567 - 선수 과목 (C++)

 

 
특정 과목을 수강하기 위한 선행과목이 있다고 했을 때, 각 과목은 최소 몇학기에 수강할 수 있는가를 구하는 문제이다.
A->B 의 선행관계가 성립된다면, A와 B를 같은 학기에 들을 수 없기 때문에 A를 1학기에 들었다면, B는 최소 2학기에 들을 수 있다.

 

문제 풀이

해당 문제는 위상 정렬을 활용한 대표적인 문제이다.
위상 정렬을 모른다면, 아래 링크를 클릭하여 위상 정렬을 알아보고 오자.
알고리즘 - 위상 정렬 (tistory.com)
 
위상정렬을 알고 있다면, 어려운 것 없이 해결할 수 있다.
진입차수가 0이되는 과목에 대해 queue에 {과목, 수강학기} 페어를 값으로 삽입한 뒤, 추가적으로 진입차수가 0이 되는 과목들은 {과목, 수강학기 + 1}의 값으로 queue에 삽입하며 queue가 빌 때 까지 반복하면 된다.
 

풀이 코드

int NumSubject = 0;
int NumLink = 0;
std::cin >> NumSubject >> NumLink;

std::vector<std::vector<int>> Links(NumSubject);
std::vector<int> InDegree(NumSubject, 0);

for (int i = 0; i < NumLink; i++)
{
    int First = 0;
    int Second = 0;
    std::cin >> First >> Second;

    Links[First - 1].push_back(Second - 1);
    InDegree[Second - 1]++;
}

먼저, 입력을 받아주었다.
Link배열은 인덱스 i에 대해, i를 선행해야 시작할 수 있는 작업들을 모아둔 배열이다.
예를 들어, 1->2, 1->3  의 선행관계가 성립된다면, Link[1] 은 {2, 3}이 되는 것이다.
 
InDegree는 진입차수이다. 인덱스 i에 대해, i를 시작하기 위한 선행 작업이 몇 개가 있느냐를 저장하는 배열이다.
 

std::queue<std::pair<int, int>> Sort;
std::vector<int> Semesters(NumSubject);

for (int i = 0; i < NumSubject; i++)
{
    if (InDegree[i] == 0)
    {
         Sort.push({i, 1});
         Semesters[i] = 1;
    }
}

위상정렬을 실행하기 위한 queue를 만들었다.
queue의 원소는 {과목, 수강학기} 이다.
최초에 진입차수가 0인 과목은 1학기에 바로 들을 수 있다는 뜻이기 때문에 {과목, 1}로 queue에 삽입해주었다.
 
Order는 해당 과목을 최소 몇 학기에 수강할 수 있는가를 저장하는 배열이다. 
 

while (Sort.size() > 0)
{
    int Index = Sort.front().first;
    int CurSemester = Sort.front().second;
    Sort.pop();

    for (int i = 0; i < Links[Index].size(); i++)
    {
        int CurIndex = Links[Index][i];
        InDegree[CurIndex]--;

        if (InDegree[CurIndex] == 0)
        {
            Sort.push({ CurIndex, CurSemester + 1});
            Semesters[CurIndex] = CurSemester + 1;
        }
    }
}

이제, 본격적으로 위상정렬을 해보자.
queue에서 가장 앞의 원소 하나를 빼준다.
 
이후, 해당 과목을 선행과목으로 갖는 과목들의 진입차수를 1씩 빼주었다.
진입차수가 0이 되는 과목이 생긴다면, 해당 과목을 queue에 삽입해주었다.
해당 과목은 다음 학기에 들을 수 있으므로, 현재학기 + 1로 삽입해주었다.
 

for (int i = 0; i < NumSubject; i++)
{
    std::cout << Semesters[i] << " ";
}

return 0;

모든 작업이 끝나고, 배열의 원소를 순서대로 출력해주면 된다.
 

 

코드 전문

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumSubject = 0;
    int NumLink = 0;
    std::cin >> NumSubject >> NumLink;
    
    std::vector<std::vector<int>> Links(NumSubject);
    std::vector<int> InDegree(NumSubject, 0);

    for (int i = 0; i < NumLink; i++)
    {
        int First = 0;
        int Second = 0;
        std::cin >> First >> Second;

        Links[First - 1].push_back(Second - 1);
        InDegree[Second - 1]++;
    }

    std::queue<std::pair<int, int>> Sort;
    std::vector<int> Semesters(NumSubject);

    for (int i = 0; i < NumSubject; i++)
    {
        if (InDegree[i] == 0)
        {
            Sort.push({i, 1});
            Semesters[i] = 1;
        }
    }

    while (Sort.size() > 0)
    {
        int Index = Sort.front().first;
        int CurSemester = Sort.front().second;
        Sort.pop();

        for (int i = 0; i < Links[Index].size(); i++)
        {
            int CurIndex = Links[Index][i];
            InDegree[CurIndex]--;

            if (InDegree[CurIndex] == 0)
            {
                Sort.push({ CurIndex, CurSemester + 1});
                Semesters[CurIndex] = CurSemester + 1;
            }
        }
    }
    
    for (int i = 0; i < NumSubject; i++)
    {
        std::cout << Semesters[i] << " ";
    }

    return 0;
}