예제: 단어 제한 끝말잇기
끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서 사용할 수 있는 단어들의 목록이 주어질 때, 단어들을 전부 사용하고 게임이 끝날 수 있는지, 그럴 수 있다면 어떤 순서로 단어를 사용해야 하는지를 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 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) 오일러 서킷 : 쉽게 말해, 한붓 그리기가 가능한 그래프(ex: a -> b -> c -> a)
2) 오일러 트레일 : 쉽게 말해, 한붓 그리기가 가능한 그래프에서 지작점과 끝점의 edge를 뺀 것(ex: a -> b-> c) -
오일러 서킷/트레일 판별법
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) -
구현시 주의점
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를 사용해서 단어를 찾아내려다 성공도 못하고 엄청난 시간을 소모했다. 과감히 메모리 할당을 해보는것도 때로는 좋지 않을까.. 하는 생각이 든다.
