각 아이템 간의 선후 관계를 통해 최종적인 순서를 결정짓는 위상정렬 문제이다.
일반적인 위상정렬은 답이 여러개가 나올 수 있다. 왜냐하면 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;
}
'매일매일 코테풀기 (일시 중단!)' 카테고리의 다른 글
| (2024-10-31) 5 문제 : 백준 - 1103 (게임) (0) | 2024.10.31 |
|---|---|
| (2024-10-31) 4 문제 : 백준 - 21940 (가운데에서 만나기) (0) | 2024.10.31 |
| (2024-10-31) 2 문제 : 백준 - 2352 (반도체 설계) (0) | 2024.10.31 |
| (2024-10-31) 1 문제 : 백준 - 1818 (책 정리) (0) | 2024.10.31 |
| (2024-10-30) 2 문제 : 백준 - 2812 (크게 만들기) (0) | 2024.10.30 |
