알고리즘 문제해결 전략 Chapter 28 - DICTIONARY(C++)

madpotato1713·2020년 1월 25일
0

알고리즘

목록 보기
31/76

예제: 고대어 사전

아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, 아니면 알파벳들의 순서가 영어와 서로 다른 것인지를 알고 싶어합니다.

일리노이 존스는 이 언어에서는 알파벳들의 순서가 영어와 서로 다를 뿐, 사전의 단어들은 사전 순서대로 배치되어 있다는 가설을 세웠습니다. 이 가설이 사실이라고 가정하고, 단어의 목록으로부터 알파벳의 순서를 찾아내려고 합니다.

예를 들어 다섯 개의 단어 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(zyxwvutsrqponmjigklhfedcba)
abcdefghijklmnopqrstuvwxyz(zyxwvusrqpnmlkjhgfdeiotcba)

풀이

이 문제는 깊이 우선 탐색을 사용하면서도, 위상정렬 개념이 들어간 DFS 문제이다.

필자 또한 위상 정렬 구현을 처음 접해보아서 긴장했으나, 위상정렬은 DFS가 끝날 때 그 vertex를 저장해준 뒤 역순으로 써주면 끝이다. 이해와는 별개로 구현은 간단했다.

이 문제는 DAG(Directed Acyclic Grapth, 사이클 없는 방향 그래프)만 잘 구현해 낸다면 나머지는 일반적인 재귀함수를 사용한 깊이 우선 탐색 구현 방법과 유사하므로 어렵지 않았다.

그러나, 역시 이해... 이해가 딸린 필자는 헛갈릴 수 있는 입출력 예제와 문제 내용에 속아버려서 삽질을 해버리고 말았다. 위 예제 출력부에서도 써놓았듯이 예제 입력에서 유추할 수 있는 알파벳 순서만 잘 지켜준다면 나머지는 상관 없는지라, 답은 여러개일 수 있다.

DAG를 구현하기 위해 필자는 26x26 int 배열을 선언하고(알파벳이 26개 이므로) 예제에서 나온 string을 두 개씩 비교하였다.

전체적인 소스코드는 아래와 같다.

소스 코드

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

using namespace std;

int adj[26][26];
int visited[26];
vector<int> order;

void setAdj(const vector<string>& words) {
	memset(adj, 0, sizeof(adj));

	for (int i = 0; i < words.size() - 1; i++) {
		int length = min(words[i].size(), words[i + 1].size());
		for (int j = 0; j < length; j++) {
			if (words[i][j] != words[i + 1][j]) {
				adj[words[i][j] - 'a'][words[i + 1][j] - 'a'] = 1;
				break;
			}
		}
	}
}

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

	for (int i = 0; i < 26; i++) {
		if (adj[vertex][i] && !visited[i]) {
			dfs(i);
		}
	}

	order.push_back(vertex);
}

void dfsAll() {
	memset(visited, 0, sizeof(visited));

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

	reverse(order.begin(), order.end());

	for (int i = 0; i < 26; i++) {
		for (int j = i + 1; j < 26; j++) {
			if (adj[order[j]][order[i]]) {
				cout << "INVALID HYPOTHESIS" << endl;
				return;
			}
		}
	}


	for (int i = 0; i < 26; i++) {
		cout << (char)(order[i] + 'a');
	}
	cout << endl;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		int N;
		cin >> N;
		vector<string> words(N);
		for (int i = 0; i < N; i++) {
			cin >> words[i];
		}

		setAdj(words); //DAG(Directed Acyclic Grapth) 만들기
		dfsAll();
	}

	return 0;
}

풀이 후기

스택을 사용한 깊이 우선 탐색을 이용한 문제들은 필자도 몇 번 풀어보았지만, 이번 문제는 위상정렬 개념이 들어간 깊이 우선 탐색 문제였다.

알고리즘 문제해결 전략 도서에서는 스택 대신 재귀함수를 사용하는데, 필자도 이 도서 덕분에 다이나믹 프로그래밍을 많이 접하며 재귀함수를 많이 다루어서 그런지 재귀함수를 사용한 DFS 구현을 이해하는데 큰 어려움은 없었다.

다음에 이 문제를 풀 때 적용해 보고 싶은것은, 지금은 26개의 알파벳을 모두 검사하지만 나열된 단어들은 그렇게 만지가 않기 때문에 vector를 써서 동적으로 풀어봐야겠다.

profile
개발자 성장일기

0개의 댓글