[algostop] 고대어 사전 (c++)

출처 : algospot.com :: DICTIONARY

algospot.com :: DICTIONARY

풀이 방법

각 단어를 비교해가며 먼저 나온 단어랑 바로 뒤에 나온 단어랑 앞글자 부터 비교해 가며 다른 글자가 나올시 

앞 단어의 철자에서 뒤 단어의 철자로 가는 간선을 추가해주는 작업을 해서 그래프를 만든다.

그리고 위상 정렬을 이용해야 한다 위상정렬은 dfs에서 마지막에 재귀호출이 끝날 때 현재 지점을 반환해주면서

마지막에 반환된 값을 뒤집어 주면 된다.

만약 그래프가 DAG가 아니라면 빈벡터를 반환하여야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>


using namespace std;

vector<vector<int>> adj;
vector<int> visited, seen, order;

void makeGraph(vector<string>& words) {
	adj = 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[i + 1].size());
		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';
				adj[a][b] = 1;
				break;
			}
			
		}	
	}
}

void dfs(int here) {
	seen[here] = 1;
	for (int there = 0; there < adj.size(); there++) {
		if (adj[here][there] && !seen[there]) {
			dfs(there);
		}
	}	
	order.push_back(here);
}

vector<int> topologicalSort() {
	int m = adj.size();
	seen = vector<int>(m, 0);
	order.clear();
	for (int i = 0; i < m; i++) if (!seen[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 (adj[order[j]][order[i]])
				return vector<int>();
		}
	}
	// 없는 경우라면 깊이 우선 탐색에서 얻은 순서를 반환한다
	return order;
}

int main() {
	int c;
	cin >> c;
	while (c--) {
		vector<string> words;
		int n;
		cin >> n;
		while (n--) {
			string str;
			cin >> str;
			words.push_back(str);
		}
		makeGraph(words);
		vector<int> ans = topologicalSort();
		if (ans.empty()) cout << "INVALID HYPOTHESIS\n";
		else {
			for (int i = 0; i < ans.size(); i++) {				
				cout << char(ans[i] + 'a');
			}
			cout << endl;
		}

	}
	return 0;
}