알고스팟 DICTIONARY 고대어 사전

먼저 그래프의 표현을 어떻게 해야할 지 정해야 한다. 정점의 갯수가 26(알파벳개수)^2 = 676, 간선의 갯수가 최대 1000000개까지 나올 수 있으므로 인접행렬, 인접리스트 모두 좋지만 인접행렬로 표현하는 것이 더 나을 수 있다

 

순서가 정해진 위상정렬 문제로, 반드시 사이클 검사와 마지막에 indegree 검사는 필수가 된다

 

문제: https://algospot.com/judge/problem/read/DICTIONARY

깃허브주소: https://github.com/surinoel/boj/blob/master/DICTIONARY.cpp

 

	#include <queue>
	#include <tuple>
	#include <string>
	#include <vector>
	#include <cstring>
	#include <iostream>
	using namespace std;
	vector<string> vs[26];
	int mat[26][26];
	int indegree[26];
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int tc;
	cin >> tc;
	while (tc--) {
	memset(indegree, 0, sizeof(indegree));
	for (int i = 0; i < 26; i++) {
	vs[i].clear();
	for (int j = 0; j < 26; j++) {
	mat[i][j] = 0;
	}
	}
	int n;
	cin >> n;
	vector<string> arr;
	for (int i = 0; i < n; i++) {
	string s;
	cin >> s;
	arr.push_back(s);
	vs[s.front() - 'a'].push_back(s);
	}
	int x = arr[0].front() - 'a';
	for (int i = 1; i < n; i++) {
	int y = arr[i].front() - 'a';
	if (x != y) {
	indegree[y] = 1; // 알파벳이 바뀌었을 때
	mat[x][y] = 1;
	x = y;
	}
	}
	for (int i = 0; i < 26; i++) {
	if (vs[i].size() > 1) {
	string s1 = vs[i][0];
	for (int v = 1; v < vs[i].size(); v++) {
	string s2 = vs[i][v];
	int len = s1.size() > s2.size() ? s2.size() : s1.size();
	for (int k = 1; k < len; k++) {
	if (s1[k] != s2[k]) {
	int x = s1[k] - 'a';
	int y = s2[k] - 'a';
	if (mat[x][y] == 0) {
	mat[x][y] = 1;
	indegree[y] += 1;
	}
	break;
	}
	}
	s1 = s2;
	}
	}
	}
	vector<char> ans;
	queue<int> q;
	for (int i = 0; i < 26; i++) {
	if (indegree[i] == 0) {
	q.push(i);
	ans.push_back('a' + i);
	}
	}
	bool ok = true;
	for (int i = 0; i < 26; i++) {
	if (q.empty()) {
	ok = false;
	break;
	}
	int ch = q.front();
	q.pop();
	for (int i = 0; i < 26; i++) {
	if (mat[ch][i]) {
	int y = i;
	if (--indegree[y] == 0) {
	q.push(y);
	ans.push_back(y + 'a');
	}
	}
	}
	}
	for (int i = 0; i < 26; i++) {
	if (indegree[i] > 0) {
	ok = false;
	break;
	}
	}
	if (!ok) {
	cout << "INVALID HYPOTHESIS\n";
	}
	else {
	for (int i = 0; i < ans.size(); i++) {
	cout << ans[i];
	}
	cout << '\n';
	}
	}
	return 0;
	}

view raw DICTIONARY.cpp hosted with ❤ by GitHub