[종만북] 문제: WORDCHAIN
서론
문제 설명
단어 $n(1 \leq n \leq 100)$개가 주어져 단어의 끝 문자와 다음 단어의 첫 문자가 같게 연속적으로 말해야 합니다.
단어들을 전부 사용해서 말할 수 있으면 어떤 순서로 단어를 사용해야 하는지 출력하고,
사용할 수 없으면, IMPOSSIBLE을 출력합니다.
문제 유형
DFS를 활용하여 오일러 경로(Euler Trail) 문제를 풀어봅시다.
naive하게 접근할 수 있을까
무식하게 단어 $n$개를 Vertex라 생각하고, 방향 그래프를 만들어 볼 수 있습니다.
그러면 각 정점에 대해 딱 한번만 접근하면 되는 그래프 문제로 바꿀 수 있습니다.
이것을 헤밀토니안 경로(Hamiltonian path) 문제라고 합니다.
그런데, 이 아이디어를 구현하기 위해서는 뭔가 마땅한 아이디어가 떠오르지 않습니다.
실제로, 이 문제는 NP-문제여서 풀 수 있는 방법이 조합 탐색밖에 없습니다. 그러면 최악의 경우, 시간복잡도는 $O(n!)$입니다.
이런 시간복잡도로는 답을 구할 수 없기 때문에 다른 알고리즘을 생각해봅시다.
다르게 접근
끝말잇기는 굳이 단어의 처음과 끝부분을 제외하면 남은 부분은 필요가 없어 보입니다.
그러면, 문자 $\to$ 문자로 단어를 재정의 할 수 있을 것 같습니다.
그럼, 문제를 변형해서 $G = (V, E)$, Vertex는 영문자, Edge는 단어로 생각해서
한 번의 trail로 모든 Edge를 방문하는 문제로 바꿀 수 있습니다.
오일러 경로
여러 정점에서 정점으로 이어진 길를 한 번만 사용해서 모든 길을 방문할 수 있을까요?
방문할 수 있으면, 이를 오일러 경로라고 합니다.
증명은 생략하고, 핵심만 말하면 다음과 같은 경우에 오일러 경로임을 알 수 있습니다.
- 모든 정점에 대해, 들어가는 길(In-Degree)과 나가는 길(out-Degree)의 수가 모두 같습니다.
- 한 정점은, 들어가는 길이 나가는 길에 비해 하나 더 많고, 반대로 한 정점은 나가는 길이 들어가는 길보다 하나 더 많습니다, 나머지 정점에 대해서는 1번 조건을 만족합니다.
어떤 경우에 오일러 경로가 아닐까?
위 성질을 이용해서, 다음과 같은 경우에는 오일러 경로가 아니겠습니다.
- source와 sink가 존재한다면, 각각 유일하고, 둘다 존재하거나, 존재하지 않아야함.
- 들어가는 길과 나가는 길의 차이가 2개 이상이라면, 오일러 경로가 아님.
- 만약 DFS를 수행해서 남은 edge가 존재 시, 오일러 경로가 아님.
DFS로 어떻게 오일러 경로를 찾을 수 있을까
가능한 한 방향으로 끝까지 내려간 후, 더 이상 갈 곳이 없을 때 해당 정점을 결과에 추가하고, 되돌아오면서 방문했던 모든 정점을 결과에 추가하는 방식으로,
모든 간선을 정확히 한 번씩 방문하는 경로를 만들어내는 것입니다.
여기서 재귀 호출은 간선을 사용하여(즉 제거한다는 뜻), 입니다. 다음 정점으로 이동하고, “더 이상 이동할 수 없을 때” 경로에 정점을 추가하는 역할을 합니다.
이때, 모든 간선이 한 번씩 사용되므로, 최종적으로 결과에 저장된 정점 순서(역순)를 뒤집으면 오일러 경로가 완성됩니다.
이를 Hierholzer 알고리즘이라 합니다.
알고리즘 구상
알고리즘 설계
- 입력을 받아 전처리를 합니다. 이때, 그래프는 인접 행렬 형태로 표현합니다.
- 그래프의 Vertex에 대해 in-degree와 out-degree를 비교하여, 오일러 경로가 맞는지 아닌지를 구별하고, source와 source가 없을 경우 시작 Vertex를 찾습니다.
- DFS를 수행하여 Vertex의 순서를 얻습니다.
- 얻은 Vertex의 순서에 대해서, 뒤에서부터 edge를 복원하며 문자열의 순서를 얻습니다.
시간 복잡도
입/출력을 제외하면, DFS함수가 시간 복잡도를 지배합니다.
| 이 DFS함수는 $G = (V, E), O( | V | + | E | )$에 비례하니, $ | V | = 26$, $ | E | = n$이므로 시간 복잡도는 $O(n)$이라고 볼 수 있습니다. |
알고리즘 구현
eulerTour()
오일러 경로를 구하는 DFS 함수입니다.
1
2
3
4
5
6
7
8
9
10
11
void eulerTour(int u) {
for (int v = 0; v < 26; v++) {
while (adj[u][v] > 0) {
adj[u][v]--;
// outDegree[u]--;
// inDegree[v]--;
eulerTour(v);
}
}
path.push_back(u);
}
main()
전체적인 알고리즘이 돌아가는 main()입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
int main() {
fastIO;
int C;
cin >> C;
while (C--) {
memset(adj, 0, sizeof(adj));
memset(inDegree, 0, sizeof(inDegree));
memset(outDegree, 0, sizeof(outDegree));
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
graph[i][j].clear();
}
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> input;
int u = input[0] - 'a', v = input[input.size() - 1] - 'a';
graph[u][v].push_back(input);
adj[u][v]++;
outDegree[u]++;
inDegree[v]++;
}
bool can = true;
int source = -1, sink = -1, start = -1;
for (int i = 0; i < 26; i++) {
if (outDegree[i] && start == -1) start = i;
if (outDegree[i] - inDegree[i]) {
if (outDegree[i] - inDegree[i] == 1 && source == -1) {
source = i;
continue;
}
if (outDegree[i] - inDegree[i] == -1 && sink == -1) {
sink = i;
continue;
}
can = false;
break;
}
}
source = source != -1 ? source : start;
path.clear();
eulerTour(source);
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
if (adj[i][j] > 0) {
can = false;
break;
}
}
}
if (!can) {
cout << "IMPOSSIBLE\n";
continue;
}
for (int i = path.size() - 2; i >= 0; i--) {
cout << *(graph[path[i + 1]][path[i]].end() - 1) << " ";
graph[path[i + 1]][path[i]].pop_back();
}
cout << "\n";
}
return 0;
}
최종 코드
여기에서 확인하세요!