28.2 문제: 고대어 사전(ID: DICTIONARY)

문제

아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, 아니면 알파벳들의 순서가 영어와 서로 다른 것인지를 알고 싶어합니다.
일리노이 존스는 이 언어에서는 알파벳들의 순서가 영어와 서로 다를 뿐, 사전의 단어들은 사전 순서대로 배치되어 있다는 가설을 세웠습니다. 이 가설이 사실이라고 가정하고, 단어의 목록으로부터 알파벳의 순서를 찾아내려고 합니다.
예를 들어 다섯 개의 단어 gg, kia, lotte, lg, hanhwa 가 사전에 순서대로 적혀 있다고 합시다. gg가 kia보다 앞에 오려면 이 언어에서는 g가 k보다 앞에 와야 합니다. 같은 원리로 k는 l앞에, l은 h앞에 와야 한다는 것을 알 수 있지요. lotte 가 lg 보다 앞에 오려면 o가 g 보다 앞에 와야 한다는 것도 알 수 있습니다. 이들을 종합하면 다섯 개의 알파벳 o, g, k, l, h 의 상대적 순서를 알게 됩니다.
사전에 포함된 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 사전에 포함된 단어의 수 N (1 <= N <= 1000) 이 주어집니다. 그 후 N 줄에 하나씩 사전에 포함된 단어가 순서대로 주어집니다. 각 단어는 알파벳 소문자로 구성되어 있으며, 길이는 1 이상 20 이하입니다. 중복으로 출현하는 단어는 없습니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 만약 알파벳들의 순서에 모순이 있다면 "INVALID HYPOTHESIS"를 출력하고, 모순이 없다면 26개의 소문자로 알파벳들의 순서를 출력합니다. 만약 가능한 순서가 여러 개 있다면 아무 것이나 출력해도 좋습니다.

예제 입력

3
3
ba
aa
ab
5
gg
kia
lotte
lg
hanhwa
6
dictionary
english
is
ordered
ordinary
this

예제 출력

INVALID HYPOTHESIS
ogklhabcdefijmnpqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

First Thoughts

먼저 단어를 벡터에 입력한다. 입력받은 벡터에서 단어를 양옆으로 비교하는데 두 단어가 서로 다른 알파벳을 가르킬 때까지 비교한다. 그리고 알파벳의 순서를 저장하는 벡터에서 특정 알파벳이 있는지 찾고 그를 바탕으로 새로운 알파벳을 삽입할 위치를 탐색한다.

My Code

#include <iostream>
#include <vector>
#include <iterator>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
vector <string> dic;
vector <char> alphabet;
void order1() {
	int i;
	for (i = 0; i < (dic.size()-1); i++) {
		int j = 0;
		while (j<dic[i].size()&&j<dic[i+1].size()&&dic[i][j] == dic[i + 1][j])
			j++;
		if (j == dic[i].size() || j== dic[i + 1].size())
			continue;
		vector<char>::iterator iter1,iter2;
		iter1 = find(alphabet.begin(), alphabet.end(), dic[i][j]);
		iter2 = find(alphabet.begin(), alphabet.end(), dic[i + 1][j]);
		if (iter1 != alphabet.end() && iter2 == alphabet.end()) {
			++iter1;
			alphabet.insert(iter1, dic[i + 1][j]);
		}
		else if (iter1 == alphabet.end() && iter2 != alphabet.end()) 
			alphabet.insert(iter2, dic[i][j]);
		else if (iter1 == alphabet.end() && iter2 == alphabet.end()) {
				alphabet.push_back(dic[i][j]);
				alphabet.push_back(dic[i+1][j]);
		}
		else {
			if (iter1 < iter2)
				continue;
			else {
				printf("INVALID HYPOTHESIS\n");
				return;
			}
		}
	}
	for (char a = 'a'; a <= 'z' ; a++) {
		if(find(alphabet.begin(),alphabet.end(),a)==alphabet.end())
			alphabet.push_back(a);
	}
	for (int i = 0; i < alphabet.size(); i++) {
		printf("%c", alphabet[i]);
	}
	printf("\n");
}
int main() {
	int C;
	int n;
	string word;
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> word;
			dic.push_back(word);
		}
		order1();
		dic.clear();
		alphabet.clear();
	}
}

Answer Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
vector<vector<int>> adj;
void makeGraph(const vector<string>& words) {
	adj = vector<vector<int>>(26, vector<int>(26, 0));
	for (int j = 1; j < words.size(); j++) {
		int i = j - 1;
		int len = min(words[i].size(), words[j].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;
			}
		}
	}
}
vector<int> seen, order;
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);
}
//adj에 주어진 그래프를 위상정렬
//그래프기 DAG가 아니라면 빈 벡터 반환
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;
}
void print_order(vector<int> order) {
	if (order.empty())
		printf("INVALID HYPOTHESIS\n");
	else {
		for (int i = 0; i < order.size(); i++) {
			printf("%c", order[i]+'a');
		}
		printf("\n");
	}
}
int main() {
	int C;
	int n;
	vector<string>words;
	string s;
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> s;
			words.push_back(s);
		}
		makeGraph(words);
		print_order(topologicalSort());
		words.clear();
	}
}

Difference & Faults

주제에서 완전 벗어난 풀이

항상 문제를 풀기 전에 내가 지금 어떤 내용을 공부하고 있는지 어떤 내용을 배웠는지 생각하며 풀어야한다. 안타깝게도 이번 문제에서 나는 무작정 내가 풀고 싶은대로 풀었다. 아이디어 자체는 매우 직관적이고 쉽지만 나의 풀이는 틀렸다. 정확한 반례를 찾지는 못했지만 아마 알파벳을 insert하는 부분에서 틀린 거 같다. 나는 insert하는 위치를 항상 바로 뒤나 바로 앞으로 하였는데 사실상 내가 넣는 위치보다 더 앞이거나 더 뒤일 수도 있는것이다. 그래서 나의 코드대로하면 맞는 순서를 invalid라고 출력할 수 있는 것이다.

인접행렬의 사용

해제 코드는 두 알파벳 사이의 관계를 인접행렬로 표현하였다. 그 과정에서 알파벳을 수치화시켰는데 이 과정이 답을 보면 뻔하지만 막상 내가 생각하려고 하면 힘든 거 같다. 그래서 문자와 문자 사이의 관계를 인덱스화 시켰다는 점도 눈여겨볼만하다.

위상정렬

위상정렬에 대한 개념확립과 구현에 대한 이해가 더 필요할 거 같다. 이는 "알고리즘 이론" 파트에서 참고하길 바란다.

Impressions

문자들의 관계를 인접행렬로 표현하고 이를 그래프로 표현한 것이 신기하다. 또한 깊이 우선 탐색을 이용하여 위상 정렬을 하는 것이 아직은 이해가 안가지만 이 또한 새로운 부분이었다.

Summary

위상정렬을 잘 이해하고 있는지 코드로 구현이 가능한지 확인하는 문제같다. 위상정렬을 전에 접해본 사람이라면 쉽게 풀 수 있는 문제같다. 일단 그래프를 처음 배워보는 것이니까 가벼운 마음으로 한 번 보고 복습할 때 완전히 이해가되길 바란다.