(2024-10-31) 3 문제 : 백준 - 23059 (리그 오브 레게노)

 

각 아이템 간의 선후 관계를 통해 최종적인 순서를 결정짓는 위상정렬 문제이다.

 

일반적인 위상정렬은 답이 여러개가 나올 수 있다. 왜냐하면 1과 2를 지어야 3을 지을 수 있는 상황에선 (1, 2, 3)도 가능하지만 (2, 1, 3)도 가능하기 때문이다. 하지만 이 문제는 사전순으로 아이템을 구매한다는 조건 때문에 답은 하나밖에 나올 수 없다. 그렇기 때문에 단순한 위상정렬로 끝내는 것이 아니라 각 아이템의 우선순위를 구해서 정렬까지 해 준 뒤에 답을 출력해야 한다.

 

 

예를 들어 예제 1번은 이런 식의 관계도가 나오는데, 가장 처음에 구매할 수 있는 3개의 아이템들 (goredrinker, stridebreaker, riftmaker)는 order가 0이고 galeforce는 order가 1이고 everfrost는 order가 2라고 매길 수 있다.

그렇다면 각 order에 대해 정렬을 수행한 뒤 출력해주면 된다.

 

그리고, 이 문제는답을 구할 수 없는 경우도 있는데 그 경우는 예외 처리를 해주어야 한다.

 

Case 1) Indegree가 0인 아이템이 없는 경우 (무한 순환)

Case 2) 위상정렬을 수행한 아이템의 수보다 실제 아이템의 수가 더 많은 경우 (무한 순환 싸이클이 중간에 포함된 경우)

 

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>

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

int main()
{
    Init();

    int NumRelation = 0;
    std::cin >> NumRelation;

    std::unordered_map<std::string, int> InDegree;
    std::map<int, std::vector<std::string>> Order;

    std::unordered_map<std::string, std::vector<std::string>> NextItems;

    for (int i = 0; i < NumRelation; i++)
    {
        std::string Prev = "", Next = "";
        std::cin >> Prev >> Next;

        InDegree.insert({ Prev, 0 });
        InDegree[Next]++;

        NextItems[Prev].push_back(Next);
    }

    std::queue<std::pair<std::string, int>> Queue;
    
    for (auto Iter : InDegree)
    {
        if (Iter.second == 0)
        {
            Queue.push({ Iter.first, 0 });
            Order[0].push_back(Iter.first);
        }
    }

    if (Queue.size() == 0)
    {
        std::cout << -1;
        return 0;
    }

    int EraseCount = 0;

    while (Queue.size() > 0)
    {
        std::string ItemName = Queue.front().first;
        int ItemOrder = Queue.front().second;

        Queue.pop();

        EraseCount++;

        for (const std::string& NextItem : NextItems[ItemName])
        {
            int NextInDegree = --InDegree[NextItem];

            if (NextInDegree == 0)
            {
                Queue.push({ NextItem, ItemOrder + 1 });
                Order[ItemOrder + 1].push_back(NextItem);
            }
        }
    }

    if (EraseCount != InDegree.size())
    {
        std::cout << -1;
        return 0;
    }

    for (auto Pair : Order)
    {
        std::sort(Pair.second.begin(), Pair.second.end());

        for (auto Item : Pair.second)
        {
            std::cout << Item << "\n";
        }
    }

    return 0;
}