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

madpotato1713·2020년 2월 2일
0

알고리즘

목록 보기
35/76

예제: 단어 제한 끝말잇기

끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서 사용할 수 있는 단어들의 목록이 주어질 때, 단어들을 전부 사용하고 게임이 끝날 수 있는지, 그럴 수 있다면 어떤 순서로 단어를 사용해야 하는지를 계산하는 프로그램을 작성하세요.

입력
입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 게임에서 사용할 수 있는 단어의 수 N (1 <= N <= 100) 이 주어집니다. 그 후 N 줄에 하나씩 게임에서 사용할 수 있는 단어가 주어집니다. 각 단어는 알파벳 소문자로 구성되어 있으며, 길이는 2 이상 10 이하입니다. 중복으로 출현하는 단어는 없습니다.

출력
각 테스트 케이스마다 한 줄을 출력합니다. 만약 모든 단어를 사용하고 게임이 끝나는 방법이 없다면 "IMPOSSIBLE" 을 출력하고 (따옴표 제외), 방법이 있다면 사용할 단어들을 빈 칸 하나씩을 사이에 두고 순서대로 출력합니다. 방법이 여러 개 있다면 그 중 아무 것이나 출력해도 좋습니다.

예제 입력

3
4
dog
god
dragon
need
3
aa
ab
bb
2
ab
cd

예제 출력

need dog god dragon
aa ab bb
IMPOSSIBLE

풀이

처음 이 문제를 접했을 때, 난이도 '하' 라고 적혀있길래 지난번에 풀었던 DICTIONARY(고대어 사전) 문제에 오일러 서킷과 트레일 개념이 더해진 것이겠거니, 했다.

하지만, 그 오일러 서킷과 트레일 개념을 제대로 이해 못해서 아주 고생한 문제이다.
그래프의 깊이 우선 탐색과 유사하지만, 오일러 개념을 모른다면 매우 어려운 문제가 될 것이다.

소스코드를 일일이 분석하기는 그렇고, 필자가 해맸던 개념을 알아보자.

  1. 오일러 서킷/트레일
    1) 오일러 서킷 : 쉽게 말해, 한붓 그리기가 가능한 그래프(ex: a -> b -> c -> a)
    2) 오일러 트레일 : 쉽게 말해, 한붓 그리기가 가능한 그래프에서 지작점과 끝점의 edge를 뺀 것(ex: a -> b-> c)

  2. 오일러 서킷/트레일 판별법
    1) 각 vertex에 들어오는 edge의 개수(이하 in), 나가는 edge(이하 out)의 개수를 센다.
    2) 오일러 서킷이라면, 각 vertex의 in과 out의 개수가 같아야 한다(in == out)
    3) 오일러 트레일이라면, 시작점과 끝점을 제외하고 vertex의 in과 out의 개수가 같아야 한다. 또한, 시작점과 끝점의 in과 out의 차는 1이다.(시작점 in + 1 = 끝점 in, 시작점 out = 끝점 out + 1)

  3. 구현시 주의점
    1) 오일러 서킷은 어느 vertex에서 시작하나 답을 구할 수 있고, reverse도 할 필요가 없다. 말했듯이 한붓그리기가 가능하기 때문에.
    2) 오일러 트레일은 시작점에서 시작해야하만 답을 구할 수 있다. 또한, 끝에 reverse를 해 주어야 한다.

이들을 잘 조합해서 구현해주어야 하고, 행렬 또는 벡터를 charater와 맵핑하여 가지고 놀기 때문에 오타 등에 매우 주의해 주어야 한다.

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

소스 코드

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

using namespace std;

int N;
vector<string> words;
int adj[26][26];
int outEdge[26], inEdge[26];
vector<string> wordsMap[26][26];
vector<int> order;

void init();
void makeAdj();
int isEuler();
void getEulerCircuitOrTrail(int);
void getEuler(int);
void dfsAll();

int main() {
	
	int testCase;
	cin >> testCase;
	for (int tc = 0; tc < testCase; tc++) {
		cin >> N;

		init();
		for (int i = 0; i < N; i++) {
			cin >> words[i];
		}

		dfsAll();
	}

	return 0;
}

void init() {
	words = vector<string>(N);
	memset(adj, 0, sizeof(adj));
	memset(outEdge, 0, sizeof(outEdge));
	memset(inEdge, 0, sizeof(inEdge));
	for (int y = 0; y < 26; y++) {
		for (int x = 0; x < 26; x++) {
			wordsMap[y][x].clear();
		}
	}
	order.clear();
}

void makeAdj() {
	for (int i = 0; i < words.size(); i++) {
		int start = words[i][0] - 'a';
		int end = words[i][words[i].size() - 1] - 'a';
		//adj
		adj[start][end]++;
		//in.out
		outEdge[start]++;
		inEdge[end]++;
		//word
		wordsMap[start][end].push_back(words[i]);
	}
}

int isEuler() {
	//차이나는 정점은 둘 다 존재하거나 없음
	//차이나는 정점은 처음과 끝 두개만 존재
	//두 개의 차는 1
	int diffOut = 0, diffIn = 0;

	for (int i = 0; i < 26; i++) {
		int diff = outEdge[i] - inEdge[i];
		if (diff < -1 && diff > 1)
			return 0;
		if (diff == 1) diffOut++;
		if (diff == 1) diffIn++;
	}

	//Euler Circuit이면 1, trail이면 2를 리턴
	if (diffOut == 0 && diffIn == 0)
		return 1;
	else if (diffOut == 1 && diffIn == 1)
		return 2;

	return 0;
}

void getEuler(int here) {
	for (int next = 0; next < 26; next++) {
		while (adj[here][next] > 0) {
			adj[here][next]--;
			getEuler(next);
		}
	}

	order.push_back(here);
}

void getEulerCircuitOrTrail(int type) {
	//Euler Circuit인 경우
	if (type == 1) {
		for (int i = 0; i < 26; i++) {
			if (outEdge[i] > 0) {
				getEuler(i);
				return;
			}
		}
	}
	//Euler Trail인 경우
	else {
		for (int i = 0; i < 26; i++) {
			if (outEdge[i] - inEdge[i] == 1) {
				getEuler(i);
				return;
			}
		}
	}
}

void dfsAll() {
	makeAdj();

	int type = isEuler();
	if (!type) {
		cout << "IMPOSSIBLE" << endl;
		return;
	}

	getEulerCircuitOrTrail(type);

	//모든 정점을 방문하지 않았다면 false;
	//정점간 단어가 1개이므로, order 개수가 단어 개수보다 1 많다.
	if (order.size() != words.size() + 1) {
		cout << "IMPOSSIBLE" << endl;
		return;
	}

	//Euler circuit이면 reverse 할 필요 없으나, trail이면 해야 함
	reverse(order.begin(), order.end());

	for (int i = 0; i < order.size() - 1; i++) {
		cout << wordsMap[order[i]][order[i + 1]].back() << " ";
		wordsMap[order[i]][order[i + 1]].pop_back();
	}
	cout << endl;
}

풀이 후기

하.. 필자에겐 너무도 어려운 문제였다.
이런 문제를 풀때마다 스스로에 대한 실망감이 커지는 느낌이다. 난이도가 하라고 써져있어서 더 그런지 모르겠다. 그래도 다음번에 비슷한 유형의 문제를 풀 때는 훨씬 빨리 풀 수 있겠지..
필자는 변수를 선언해서 메모리 할당을 많이 안하려는 습성이 있다. 물론 좋은 것이겠지만, 위 풀이에서 wordsMap으로 단어들을 저장해서 하지 않고 order를 사용해서 단어를 찾아내려다 성공도 못하고 엄청난 시간을 소모했다. 과감히 메모리 할당을 해보는것도 때로는 좋지 않을까.. 하는 생각이 든다.

profile
개발자 성장일기

0개의 댓글