28.4 ~ 28.6 개념
그래프의 모든 간선을 한 번씩만 경유하여 다시 시작점으로 돌아오는 경로를 오일러 서킷이라고 하며 오일러 트레일이라는 것도 있다.
오일러 트레일은 모든 간선을 한 번 씩만 경유한다는 점에서 오일러 서킷과 유사하지만 시작점과 끝점이 달라야 된다는 점에서 차이가 있다.
오일러 서킷이 존재하기 위해서는 한정점에 대해 정점으로 들어오는 간선의 갯수와 정점에서 나가는 갯수가 일치해야 된다는 특성을 모든 정점이 만족해야 한다. 방향그래프가 아닌 무방향 그래프에서는 나가고 들어오는 것의 구분이 없기 때문에 한 정점에 연결된 간선의 갯수가 짝수이면 된다.
무방향 그래프에서 오일러 트레일을 구할 때 트레일이 a에서 시작해 b에서 끝난다고 해보자. 이때 (b, a)간선을 추가해주면 a에서 시작해 a에서 끝나는 오일러 서킷이 된다. 그리고 경로의 처음과 끝을 연결해주기 때문에 시작점과 끝점을 제외한 모든 정점에서의 차수는 짝수이고 시작점과 끝점의 차수는 홀수여야된다. 무방향에서의 오일러 트레일 존재조건은 시작점, 끝점의 차수는 홀수, 그 외의 점들에서의 차수는 짝수였다면 방향그래프에서는 이와 사뭇 다르다. 방향그래프는 간선의 상태가 두가지 있으므로 시작점에서는 나가는 간선이 들어오는 간선보다 하나 더 많아야 되고 끝점에서는 들어오는 간선이 나가는 간선보다 하나 더 많아야 된다. 그리고 시작, 끝점 이외의 정점에서는 들어오는 간선의 수와 나가는 간선의 수가 일치해야 한다.
홀수점이 하나라도 있다면 오일러 서킷이 존재하지 않는다. 그러면 역으로 오일러 서킷이 존재하지 않는다면 임의의 정점의 차수가 홀수이다 라는 명제가 성립한다라고 할 수 있을까? 명제에서 역은 항상 참은 아니므로 생각할 필요가 있다. 다행히 모든 정점이 짝수점이면서 간선들이 하나의 컴포넌트에 속한다면 항상 오일러 서킷이 존재한다.
모든 경로가 아닌 모든 정점을 한 번씩만 지나는 경로를 해밀토니안 경로라 하는데 최대 n!가지의 경우의 수를 확인해야 되기때문에 효율적이지 않다.
28.5: 단어제한 끝말잇기(WORDCHAIN)
https://algospot.com/judge/problem/read/WORDCHAIN
28.6 풀이
- 주어진 각 단어를 정점이 아닌 간선으로 갖는 방향그래프를 만든다. 이때 정점들은 알파벳 하나를 표현하게 되고 단어는 첫글자에서 마지막 글자로 가는 간선이 된다.
이 문제에서는 모든 단어들을 사용해야 한다. 그리고 오일러 트레일 or 서킷은 모든 간선들을 거쳐야 하므로 단어를 간선으로 채택하는 것은 정당해 보인다.
- 이 그래프에서 오일러 트레일 or 오일러 서킷을 찾는다.
오일러 트레일 or 오일러 서킷이기 때문에 둘 중 하나를 선택해야된다. 이때 선택을 하는 방법이 각 정점의 차수를 확인하는 것이다. 오일러 트레일의 시작점에서는 나가는 간선의 수가 들어오는 간선의 수보다 하나 더 많아야 한다. 그래서 이런 특성을 만족하는 정점이 있다면 오일러 트레일을 선택하고 없다면 오일러 서킷을 찾는 함수를 작성하면 된다.
코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int>> adj;
vector<string> grapgh[26][26];
vector<int> inDegree, outDegree;
void makeGrapgh(const vector<string>& words) {
for (int i = 0; i < 26; i++)
for (int j = 0; j < 26; j++)
grapgh[i][j].clear();
adj = vector<vector<int>>(26, vector<int>(26, 0));
inDegree = outDegree = vector<int>(26, 0); //경로의 시작점을 쉽게 찾아낼 수 있도록 하기 위해서 inDegree, outDegree사용
for (int i = 0; i < words.size(); i++) {
int a = words[i][0] - 'a';
int b = words[i].back() - 'a';
grapgh[a][b].push_back(words[i]);
adj[a][b]++;
outDegree[a]++;
inDegree[b]++;
}
}
void getEulerCircuit(int here, vector<int>& circuit) {
for (int there = 0; there < adj.size(); there++) {
while (adj[here][there] > 0) {
adj[here][there]--;
getEulerCircuit(there, circuit);
}
}
circuit.push_back(here);
}
vector<int> getEulerTrailOrCircuit() {
vector<int> circuit;
for (int i = 0; i < 26; i++)
if (outDegree[i] == inDegree[i] + 1) {
getEulerCircuit(i, circuit);
return circuit;
}
for (int i = 0; i < 26; i++)
if (outDegree[i]) {
getEulerCircuit(i, circuit);
return circuit;
}
}
bool checkEuler() {
int plus1 = 0, minus1 = 0;
for (int i = 0; i < 26; i++) {
int delta = outDegree[i] - inDegree[i];
if (delta < -1 || delta > 1)
return false;
if (delta == 1)
plus1++;
if (delta == -1)
minus1++;
}
return (plus1 == 1 && minus1 == 1) || (plus1 == 0 && minus1 == 0);
}
string solve(const vector<string>& words) {
if (!checkEuler())
return "IMPOSSIBLE";
vector<int> circuit = getEulerTrailOrCircuit();
if (circuit.size() != words.size() + 1)
return "IMPOSSIBLE";
reverse(circuit.begin(), circuit.end());
string ret;
for (int i = 1; i < circuit.size(); i++) {
int a = circuit[i - 1], b = circuit[i];
if (ret.size())
ret += " ";
ret += grapgh[a][b].back();
grapgh[a][b].pop_back();
}
return ret;
}
int main(void) {
int C, N;
vector<string> words;
string tmp;
cin >> C;
while (C--) {
cin >> N;
words.clear();
for (int i = 0; i < N; i++) {
cin >> tmp;
words.push_back(tmp);
}
makeGrapgh(words);
cout << solve(words) << endl;
}
return 0;
}