[BOJ 23059 // C++] 리그 오브 레게노

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 23059번 문제인 리그 오브 레게노이다.
문제는 아래 링크를 확인하자.

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

23059번: 리그 오브 레게노

주어진 문제의 상황을 각 아이템을 노드로, 아이템의 구입 순서 전후관계를 방향이 있는 에지로 갖는 그래프로 모델링하자. 그리고 이 그래프의 각 노드의 indegree를 미리 계산해두고, 매 아이템 구입의 순간마다 해당 차례에 구입할 수 있는 아이템과 그 다음 차례에 구입할 수 있는 아이템을 벡터와 indegree를 이용해 bfs와 같은 방식으로 구현하는 것으로 문제를 해결하자.

 

각 아이템의 이름을 map과 배열 등을 이용해 정수에 대응시켜 구현을 편리하게 하자.

 

주어지는 아이템의 종류의 개수는 관계의 수의 2배, 즉 최대 40만가지까지 주어질 수 있음에 유의하자.

 

아래는 제출한 소스코드이다.

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

int N;
int idx = 0;
map<string, int> stoidx;
string idxtos[400001];
vector<int> G[400001];
int indegree[400001];

vector<string> nxt;
string ans;
int cnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		string s1, s2; cin >> s1 >> s2;
		if (!stoidx.count(s1)) {
			idx++;
			stoidx.insert({ s1,idx }), idxtos[idx] = s1;
		}
		if (!stoidx.count(s2)) {
			idx++;
			stoidx.insert({ s2,idx }), idxtos[idx] = s2;
		}
		G[stoidx[s1]].emplace_back(stoidx[s2]);
		indegree[stoidx[s2]]++;
	}

	for (int i = 1; i <= idx; i++) {
		if (indegree[i] == 0) nxt.emplace_back(idxtos[i]);
	}
	while (!nxt.empty()) {
		sort(nxt.begin(), nxt.end());
		vector<string> tmp;
		for (auto& s : nxt) {
			ans += s + '\n', cnt++;

			int cur = stoidx[s];
			for (auto& node : G[cur]) {
				indegree[node]--;
				if (indegree[node] == 0) tmp.emplace_back(idxtos[node]);
			}
		}

		swap(nxt, tmp);
	}

	if (cnt < idx) cout << -1;
	else cout << ans;
}