[백준/BOJ] 백준 23059번 : 리그 오브 레게노

https://www.acmicpc.net/problem/23059

23059번: 리그 오브 레게노

 

아이템의 관계를 그래프로 표현하여, 위상 정렬과 같은 방법을 통해 문제를 해결했다.

 

이때 현재 구매할 수 있는 "아이템 중 아직 구매하지 않은 아이템을 모두 찾고, 찾은 아이템을 사전순으로 구매하는 과정"을 거치므로, indegree가 0 인 아이템을 모두 그래프에서 깊이를 0으로 표시하여 그래프의 탐색을 이어나갈수록 깊이가 깊어지는 것으로 표시하였으며, 아이템을 뽑을 때 "깊이의 값이 낮은 것 중, 아이템의 이름이 사전순으로 빠른 것"을 선택하도록 해서 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
using namespace std;

int n;
multimap<string, string> adj;
map<string, int> indegree;
int item_cnt = 0;
vector<string> result;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		string a, b;

		cin >> a >> b;

		if (indegree.count(a) == 0) {
			item_cnt++;
			indegree.insert(make_pair(a, 0));
		}

		if (indegree.count(b) == 0) {
			item_cnt++;
			indegree.insert(make_pair(b, 0));
		}

		adj.insert(make_pair(a, b));
		indegree[b]++;
	}

	priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq; //(depth, item이름) 오름차순

	for (map<string, int>::iterator it = indegree.begin(); it != indegree.end(); it++) {
		string item = (*it).first;

		if ((*it).second == 0) {
			pq.push(make_pair(0, item));
		}
	}



	while (!pq.empty()) {
		int here_depth = pq.top().first;
		string here = pq.top().second;
		pq.pop();

		result.push_back(here);

		for (multimap<string, string>::iterator it = adj.lower_bound(here); it != adj.upper_bound(here); it++) {
			string there = (*it).second;

			indegree[there]--;

			if (indegree[there] == 0) {
				pq.push(make_pair(here_depth + 1, there));
			}
		}
	}

	if (result.size() != item_cnt) {
		cout << -1;
	}

	else {
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << "\n";
		}
	}

	return 0;
}