(출처) https://algospot.com/judge/problem/read/WORDCHAIN
해밀토니안 경로와 오일러 서킷 or 경로
문제에서 주어지는 단어를 하나의 정점으로 바라보고 끝말잇기가 가능한 단어들 끼리는 단방향 간선을 이어주는 그래프를 그린다. 이후 정점을 모두 1번씩만 방문한 뒤 종료할 수 있으면 정답을 리턴하고, 할 수 없다면 Impossible을 리턴하는 식으로 구현하면 되지 않을까라는 생각으로 시작해보았다. 하지만 이런 식으로 그래프를 구상하면 결국은 완전탐색으로밖에 정답을 구할 수가 없었다.
이렇게 하나의 정점과 연결된 다른 정점들을 전부 탐색하고 따라가보면서 실패하면 돌아와서 재탐색하는 방법으로 구현을 한다면, 만약 N 개의 정점들끼리 모두 연결되어 있는 그래프가 주어질 때 총 N! 개의 계산횟수를 수행해야 한다. 당연히 시간초과가 나게 된다.
다른 방법이 없을까 생각해 보며 이것저것 생각해 보다 결국 포기하고 그냥 책을 참고하기로 했다.
책의 첫 단락에서부터 나와 같은 구현은 해밀토니안 경로를 찾는 방식의 구현으로 단박에 안된다고 써져있었다.
단어 자체를 하나의 정점으로 바라보는 방식이 아니라, 26개의 알파벳 글자로 정점을 구성하는 그래프를 만들어, 단어의 맨 앞글자와 맨 뒷글자를 연결하여 하나의 간선으로 표현하여 구현한다면 이번에는 모든 정점을 전부 1번씩 방문해야 되는 것이 아니라 모든 간선을 전부 1번씩 방문해야 되는 오일러 경로를 구하는 문제로 뒤바뀌게 된다.
오일러서킷 구하기
위와 같은 방법으로 모든 알파벳으로 그래프를 구성한다면 결국 오일러서킷 탐색 알고리즘을 DFS로 구현하기만 하면 된다.
이때 그래프는 26개의 알파벳 글자들을 모두 정점으로 표현한 상태이므로, 입력에 사용되지 않았던 알파벳 글자들 같은 경우, 그래프 내 간선이 전혀 존재하지 않는 동떨어진 정점(글자)으로 존재할 수도 있다.
따라서 26개의 알파벳글자를 모두 한 번씩 탐색의 첫 시작점으로 하여, 총 26번의 탐색을 진행해야 한다. 중간에 N 개의 길이의 오일러서킷을 발견하는 경우 해당 경로를 return 하고 답안으로 제출하면 된다.
동떨어진 정점들은 어차피 경로에 영향을 주지 못하므로, 해당 정점을 첫 시작으로 하는 탐색은 실패하더라도 그냥 지나치면 된다.
총 26번의 탐색 동안 N 개의 길이를 만족하는 경로를 구해내지 못했다면 해당 단어 그래프는 Impossible이 된다.
이때 주의해야 할 것은,
그래프에서 오일러서킷의 존재하고 있는 경우에만 시작점을 신경쓰지 않고 자유롭게 탐색을 진행할 수 있다는 것이다.
오일러 서킷의 경우 어느 정점에서 시작하더라도 결국 시작점으로 돌아오기 때문에 첫 시작점을 어떤 정점을 고르든 간에 상관이 없다.
하지만 시작점과 종료점이 다른 오일러경로의 경우, 오일러서킷과는 달리 시작점과 끝점이 분명히 정해져 있기 때문에 탐색을 시작할 위치를 반드시 구한 뒤 해당 점에서 탐색을 돌려주어야 한다.
만약 올바르지 않는 시작점에서 탐색을 진행시키는 경우 N 개의 경로를 전부 만들어내지 못하고 탐색이 종료되어 버린다.
이때 탐색함수 로직에는 중간에 따라가본 간선을 그래프에서 지워주는 작업이 존재하기 때문에, 만약 탐색 전 미리 간선들을 백업해놓고 탐색마다 백업시킨 뒤 작업을 진행하지 않는 이상 26번의 탐색을 돌리더라도 올바른 답을 구해내지 못한다.
26번의 탐색마다 간선을 백업하고 되돌려주는 작업은 작업비용이 비효율적이고 구현도 까다롭기 때문에, 경로 탐색을 진행하기 전에 그래프 내 오일러경로의 존재여부를 미리 판단해 줄 필요성이 있다.
판단하는 과정은 26개 알파벳 글자의 간선을 전부 세주어 차수를 계산하면 된다.
만약 들어오는 간선보다 나가는 간선보다 하나 많은 정점이 존재한다면 해당 정점은 시작점이 될 것이다. (이때, 해당 정점의 차수는 -1)
반대로 나가는 간선이 들어오는 간선보다 하나 많은 정점은 종료점이 된다. (이때, 해당 정점의 차수는 1)
그래프에 간선의 차수가 -1과 1이 되는 정점이 단 한 쌍만 존재한다면, 해당 그래프는 오일러경로가 존재한다고 판단할 수 있다.
만약 간선의 차수가 -1 미만이거나 1을 초과하는 정점이 존재한다면 무슨 짓을 하더라도 한붓그리기를 진행시킬 수 없다. 또한 차수가 -1이나 1이 되는 정점이 여러 개 존재한다고 하더라도 당연히 불가능하다.
차수가 0인 경우는 들어오는 간선과 나가는 간선이 똑같은 경우이거나, 아예 간선이 존재하지 않는 동떨어진 정점인 경우인데 어차피 동떨어진 정점의 경우는 경로에 영향을 끼치지 못하기 때문에 무시해도 된다.
(입력에 동떨어진 단어가 존재해서 해당 단어 때문에 경로를 만들지 못하는 경우도 어차피 탐색과정에서 자연스럽게 N 개 길이의 경로를 만들지 못할 것이기 때문에 자연스럽게 Impossible을 리턴할 것이다)
이렇게 차수를 계산하는 판단 과정에서 오일러경로를 발견했으면, 차수가 1인 시작점을 따로 보관한 뒤 꺼내와 해당 정점으로 바로 탐색을 진행시키면 굳이 26개의 시작점을 모두 확인해보며 탐색을 진행할 필요 없이 바로 경로를 구해낼 수 있다.
시간복잡도
해당 알고리즘은 26개의 알파벳 글자를 모두 시작점으로 하여 1번씩 탐색을 진행하므로 전체 시간복잡도는 O(26 * 탐색로직)이 된다.
이때 탐색함수는 그래프에 존재하는 간선 1개마다 무조건 1번씩 실행되고, 실행 후 확인한 간선을 제거하기 때문에 총 간선의 개수(E)만큼 실행된다. 따라서 탐색로직의 시간복잡도는 O(E * 함수내부복잡도) 이다.
함수내부에서는 현재 바라보고 있는 정점과 다른 모든 정점 V 개와의 간선연결을 확인하기 위한 총 V 번의 for문 반복로직이 존재한다. 따라서 함수내부의 시간복잡도는 O(V) 가 된다.
이때 간선 E는 모든 정점들끼리 서로 전부 연결되어 있는 최악의 경우를 생각한다면 총 V^2개가 될 것이다. 따라서 최악의 경우 탐색로직은 O(V^3)이 된다. 결국 전체 시간복잡도는 O(26 * V^3)이 되는데 문제에서 주어지는 V의 최댓값은 100이므로 충분히 해결할 수 있는 범위이다.
해밀토니안 경로 코드 (시간초과)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
vector<bool> visted;
const string IMPOSSIBLE = "IMPOSSIBLE";
int n;
//그래프 만들기 O(N^2)
void making_graph(vector<string> &words, vector<vector<int>> &graph) {
for (int i = 0; i < words.size(); i++) {
char main_word = words[i].back();
for (int j = 0; j < words.size(); j++) {
if (i == j) continue;
char target_word = words[j].front();
if (main_word == target_word) {
graph[i].push_back(j);
}
}
}
}
vector<int> wordchain(vector<vector<int>>& graph, int vertex, vector<int>& ret) {
int here = vertex;
ret.push_back(here);
visted[here] = true;
for (int i = 0; i < graph[here].size(); i++) {
int there = graph[here][i];
if (!visted[there]) {
wordchain(graph, there, ret);
if (ret.size() == n) break;
ret.pop_back();
visted[there] = false;
}
}
if (ret.size() == n) return ret;
return vector<int> ();
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
cin >> n;
vector<string> words(n);
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
words[i] = temp;
}
vector<vector<int>> graph(n);
making_graph(words, graph);
visted = vector<bool>(n, false);
vector<int> ret;
for (int i = 0; i < n; i++) {
ret = wordchain(graph, i, ret);
if (ret.size() == n) break;
}
if (ret.size() != n) cout << IMPOSSIBLE << "\n";
else {
for (int i = 0; i < n; i++) {
int target = ret[i];
if (i == ret.size() - 1) {
cout << words[target] << "\n";
}
else cout << words[target] << " ";
}
}
}
return 0;
}오일러서킷 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const string IMPOSSIBLE = "IMPOSSIBLE";
int n;
vector<int> indegree;
vector<int> outdegree;
vector<vector<vector<string>>> edge;
//그래프 만들기 O(N)
void making_graph(vector<string> &words, vector<vector<int>> &graph) {
for (int i = 0; i < words.size(); i++) {
int front = (int)words[i].front() - (int)'a';
int end = (int)words[i].back() - (int) 'a';
graph[front][end]++;
edge[front][end].push_back(words[i]);
outdegree[front]++;
indegree[end]++;
}
}
void wordchain(vector<vector<int>>& graph, int vertex, vector<string> &ret) {
int here = vertex;
for(int there = 0; there < graph.size(); there++) {
while (graph[here][there] > 0) {
graph[here][there]--;
wordchain(graph, there, ret);
ret.push_back(edge[here][there].back());
edge[here][there].pop_back();
}
}
}
int judge_circle(vector<int> &indegree, vector<int> &outdegree) {
int plus1 = 0;
int minus1 = 0;
int start = -1;
for (int i = 0; i < indegree.size(); i++) {
int degree = indegree[i] - outdegree[i];
if (degree < -1 || degree > 1) return -1;
if (degree == -1) {
minus1++;
start = i;
}
else if (degree == 1) {
plus1++;
}
}
if (minus1 == plus1) {
if (minus1 == 1) return start;
else if (minus1 == 0) return start = -1;
}
else return -2;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
cin >> n;
vector<string> words(n);
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
words[i] = temp;
}
vector<vector<int>> graph(26, vector<int>(26,0));
edge = vector<vector<vector<string>>> (26, vector<vector<string>>(26));
indegree = vector<int>(26, 0);
outdegree = vector<int>(26, 0);
making_graph(words, graph);
int judge = judge_circle(indegree, outdegree);
vector<string> ret;
if (judge == -2) {
cout << IMPOSSIBLE << "\n";
continue;
}
if( judge == -1) {
for (int i = 0; i < 26; i++) {
ret = vector<string>();
wordchain(graph, i, ret);
if (ret.size() == n) break;
}
}
if (judge >= 0) wordchain(graph, judge, ret);
if (ret.size() != n) cout << IMPOSSIBLE << "\n";
else {
for (auto i = ret.rbegin(); i < ret.rend(); i++) {
if (i == ret.rend() - 1) {
cout << *i << "\n";
break;
}
cout << *i << " ";
}
}
}
return 0;
}다른버전 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const string IMPOSSIBLE = "IMPOSSIBLE";
int n;
vector<int> indegree;
vector<int> outdegree;
vector<vector<vector<string>>> edge;
//그래프 만들기 O(N)
void making_graph(vector<string> &words, vector<vector<int>> &graph) {
for (int i = 0; i < words.size(); i++) {
int front = (int)words[i].front() - (int)'a';
int end = (int)words[i].back() - (int) 'a';
graph[front][end]++;
edge[front][end].push_back(words[i]);
outdegree[front]++;
indegree[end]++;
}
}
void wordchain(vector<vector<int>>& graph, int vertex, vector<string> &ret) {
int here = vertex;
for(int there = 0; there < graph.size(); there++) {
while (graph[here][there] > 0) {
graph[here][there]--;
wordchain(graph, there, ret);
ret.push_back(edge[here][there].back());
edge[here][there].pop_back();
}
}
}
int find_start(vector<int> &indegree, vector<int> &outdegree) {
int plus1 = 0;
int minus1 = 0;
int start = -1;
for (int i = 0; i < indegree.size(); i++) {
int degree = indegree[i] - outdegree[i];
if (degree == -1) {
minus1++;
start = i;
}
else if (degree == 1) {
plus1++;
}
}
if (minus1 == plus1 && minus1 == 1) return start;
else return -1;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
cin >> n;
vector<string> words(n);
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
words[i] = temp;
}
vector<vector<int>> graph(26, vector<int>(26,0));
edge = vector<vector<vector<string>>> (26, vector<vector<string>>(26));
indegree = vector<int>(26, 0);
outdegree = vector<int>(26, 0);
making_graph(words, graph);
int start = find_start(indegree, outdegree);
vector<string> ret;
if (start == -1) {
for (int i = 0; i < 26; i++) {
ret = vector<string>();
wordchain(graph, i, ret);
if (ret.size() == n) break;
}
}
else wordchain(graph, start, ret);
if (ret.size() != n) cout << IMPOSSIBLE << "\n";
else {
for (auto i = ret.rbegin(); i < ret.rend(); i++) {
if (i == ret.rend() - 1) {
cout << *i << "\n";
break;
}
cout << *i << " ";
}
}
}
return 0;
}기억하고 싶은 점
오일러서킷과 경로는 처음 접해보는 것이라 구현도 낯설게 느껴지고 문제를 풀 때 머리가 너무 복잡해지더라. 여러 가지 퍼즐 조각들이 아직 완전히 내재화가 돼있지 않아서 생각이 여기저기로 튀어가는 걸 바로잡는 게 너무 어려웠다.
생각해 보면 이렇게 여러 개념이 아직 많이 미숙한 상황에서, 문제에서처럼 모든 알파벳 단어를 그래프의 정점으로 삼아 구현하는 센스를 과연 떠올려 낼 수 있을까 싶다.
특히 처음 해보는 구현은 어떤 아이디어가 떠오르더라도 이렇게 해서 정말 될지, 안될지라는 확신이 바로 서지 않기 때문에 무작정 코드를 써 내려가기도 어렵다. 만약 생각난 아이디어대로 구현을 하다가 뒤늦게 잘못된 걸 깨닫게 되면 결국 다 뒤집어엎어야 되는 경우가 생기는데, 그럴 때마다 시간은 시간대로 쏟아붓고 다시 0으로 돌아간 느낌이라 그냥 컴퓨터 끄고 잠이나 자고 싶어진다.
이 문제도 난이도 하로 분류되어 있던데 절대로 한붓그리기 문제를 풀어보고 경험해보지 않았던 사람한테는 하의 난이도로 느껴지지 않을 것 같다. 아닐 수도 있지만.
