1쇄 847쪽에는 다음과 같이 쓰여 있습니다.
여기에서 눈여겨 볼 점은, 생성한 그래프에 오일러 트 레일이 존재하는지 여부를 먼저 확인하지 않는다는 것입니다. 물론 각 정점의 차수를 검사하고, 모든 간선이 서로 연결되어 있는지를 확인해서 오일러 트레 일의 존재 여부를 먼저 확인할 수도 있습니다. 그러나 어차피 오일러 트레일을 구할 거라면 더 간단한 방법이 있습니다. 우선 오일러 트레일이 존재한다고 가 정하고 트레일을 찾는 것입니다. getEulerTrailOrCircuit()은 오일러 트레일이 존재한다면 이를 반드시 찾아냅니다. 따라서 오일러 트레일의 존재 여부를 확 인할 필요 없이, 우리가 찾은 경로의 길이를 확인하는 것만으로 우리가 실패했 는지 아닌지를 알 수 있게 되지요. 이 코드는 getEulerTrailOrCircuit()을 무조 건 먼저 호출한 뒤, 이 함수가 반환하는 경로의 길이가 단어의 수와 일치하는지 확인하는 방식으로 동작합니다.
이 방법은 옳은 방법이 아닙니다. 다음과 같은 입력이 주어진다고 합시다.
3
aa
ab
ac
이 입력은 연결된 그래프이므로, 깊이 우선 탐색은 모든 간선을 방문합니다. 하지만 이것이 오일러 서킷의 존재 여부를 나타내지는 않지요. 따라서 결국 정점들의 차수를 확인하는 작업이 필수적입니다.
2쇄에서는 847쪽의 해당 문단이 다음과 같이 수정됩니다.
이렇게 그래프의 생성과 오일러 서킷 혹은 트레일을 찾는 코드를 작성하고 나면 나머지는 아주 단순합니다. 오일러 트레일이 존재하는지 확인하고, 존재한다면 출력 문자열을 계산해 반환하기만 하면 되지요. 코드 28.7이 이와 같은 코드의 구현을 보여줍니다. 생성한 그래프의 정점들의 차수를 검사하는 $checkEuler()$ 를 눈여겨 보세요. 방향 그래프에서 오일러 서킷이 있으려면 모든 정점에서 나가는 간선의 수와 들어오는 간선의 수가 같아야 하고, 트레일이 있으려면 나가는 간선이 하나 많은 시작점이 하나, 들어오는 간선이 하나 많은 끝점이 하나 있어야 합니다. 이 조건이 만족되는 경우에도 그래프가 두 개 이상으로 분리되어 있다면 오일러 서킷/트레일을 찾을 수 없으므로, 마지막에 모든 간선을 방문했는지 확인한다는 점 또한 눈여겨 보세요.
코드 28.7은 다음과 같이 바뀝니다.
// 현재 그래프의 오일러 서킷/트레일 존재 여부를 확인한다.
bool checkEuler() {
// 예비 시작점과 끝점의 수
int plus1 = 0, minus1 = 0;
for(int i = 0; i < 26; ++i) {
int delta = outdegree[i] - indegree[i];
// 모든 정점의 차수는 -1, 1 또는 0 이어야 한다.
if(delta < -1 || 1 < delta) 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) {
makeGraph(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 += graph[a][b].back();
graph[a][b].pop_back();
}
return ret;
}