[알고스팟][C++] DICTIONARY: 고대어 사전

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

(출처: 종만북)

 

임의의 알파벳 순서를 가진 사전 순서대로 정렬된 단어들을 입력받았을 때, 그 사전의 알파벳 우선순위를 출력하고 알파벳 순서에 모순이 있다면 에러 메시지를 출력하는 문제입니다.

단어들을 이용해 graph[26][26]을 만드는데, 이 때 간선 [i][j]는 알파벳 i가 j 앞에 와야됨을 의미합니다. 그래프를 만들 때 인접 단어끼리만 검사하면 됩니다.

 

그래프를 만든 뒤 DFS를 이용해 위상정렬을 한 뒤, 반환된 순서에서 오른쪽에서 왼쪽으로 가는 간선이 있는지 확인하면 됩니다. 그런 간선이 있으면 알파벳 순서에 모순이 있는 거겠죠.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

//<i, j> --> 알파벳 i가 j보다 앞에 옴
vector<vector<int> > graph;

// 주어진 단어들로부터 알파벳간의 선후관계 그래프 생성
void makeGraph(const vector<string>& words) {
	graph = vector<vector<int> >(26, vector<int>(26, 0));
	for (int j = 1; j < words.size(); ++j) {
		int i = j - 1, len = min(words[i].size(), words[j].size());
		
		// word[i]가 word[j] 앞에 오는 이유를 찾음
		for (int k = 0; k < len; ++k) {
			if (words[i][k] != words[j][k]) {
				int a = words[i][k] - 'a';
				int b = words[j][k] - 'a';

				graph[a][b] = 1;
				break;
			}
		}
	}
}


vector<int> visited, order;

void dfs(int current) {
	visited[current] = 1;

	for (int next = 0; next < graph.size(); ++next)
		if (graph[current][next] && !visited[next])
			dfs(next);
	order.push_back(current);
}

// graph를 위상정렬한 결과를 반환
// DAG가 아니라면 빈 벡터 반환
vector<int> topologicalSort() {
	int m = graph.size();
	visited = vector<int>(m, 0);
	order.clear();

	for (int i = 0; i < m; ++i)
		if (!visited[i])
			dfs(i);

	reverse(order.begin(), order.end());
	
	// 역방향 간선이 있는 경우 --> DAG가 아님
	for (int i = 0; i < m; ++i)
		for (int j = i + 1; j < m; ++j)
			if (graph[order[j]][order[i]])
				return vector<int>();

	return order;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<string> words(n);
		for (auto& w : words)
			cin >> w;
		makeGraph(words);
		auto orders = topologicalSort();
		if (orders.empty()) {
			cout << "INVALID HYPOTHESIS\n";
		}
		else {
			for (auto& o : orders)
				cout << static_cast<char>(o + 'a');
			cout << '\n';
		}
	}

	return 0;
}