어릴 적 스케치북에 별 모양이나 집 모양을 그리며, "펜을 한 번도 떼지 않고, 왔던 선을 다시 지나지 않으면서 전체 그림을 완성할 수 있을까?"라는 내기를 해본 적이 있으실 것입니다. 이 단순해 보이는 놀이는 18세기 천재 수학자 레온하르트 오일러(Leonhard Euler)가 '쾨니히스베르크의 7개 다리 문제'를 해결하기 위해 창시한 그래프 이론의 시초이자, 현대 컴퓨터 과학에서 네트워크 패킷 라우팅이나 DNA 시퀀싱 등에 폭넓게 응용되는 '오일러 경로(Eulerian Path)' 알고리즘의 뼈대입니다. 그래프 내의 모든 간선(Edge)을 단 한 번씩만 통과하여 완벽한 경로를 찾아내는 수학적 조건과, 이를 컴퓨터 코드로 우아하게 구현해 내는 하이어홀저(Hierholzer) 알고리즘의 동작 원리를 깊이 있게 파헤쳐 보겠습니다.
1. 한붓그리기의 절대적인 수학적 조건 (차수 규칙)
오일러는 그래프의 정점(Node)에 연결된 선(간선)의 개수인 '차수(Degree)'가 짝수인지 홀수인지 파악하는 것만으로, 펜을 직접 움직여보지도 않고 한붓그리기가 가능한지 불가능한지를 1초 만에 판별해 내는 위대한 공식을 세웠습니다.
1-1. 무방향 그래프에서의 차수(Degree) 판별법
간선에 방향성이 없는 일반적인 도로망이라고 가정할 때, 모든 정점의 차수를 셉니다. 홀수 개의 선이 연결된 정점을 '홀수점', 짝수 개의 선이 연결된 정점을 '짝수점'이라고 부릅니다.
- 오일러 회로 (Eulerian Circuit): 한붓그리기를 완성한 뒤, 출발했던 원래 위치로 완벽하게 되돌아오는 경로입니다. 이 회로가 존재하려면 그래프 내의 모든 정점이 100% 짝수점이어야만 합니다. 어떤 정점이든 '들어오는 선'이 있으면 반드시 '나가는 선'이 짝을 이루어야 갇히지 않기 때문입니다.
- 오일러 경로 (Eulerian Path): 출발점과 도착점이 달라도 상관없이, 모든 선을 한 번씩 긋는 경로입니다. 이 경로가 존재하려면 그래프 내에 홀수점이 정확히 0개이거나 딱 2개뿐이어야 합니다. 홀수점이 2개일 경우, 하나는 무조건 '출발점'이 되고 나머지 하나는 무조건 '도착점'이 되는 수학적 필연성을 가집니다. 홀수점이 1개이거나 3개 이상이라면 그 그래프는 절대 한붓그리기를 할 수 없습니다.
2. 하이어홀저(Hierholzer) 알고리즘의 우아한 DFS
수학적 조건이 충족되었다면, 이제 컴퓨터에게 실제로 선을 긋는 경로(순서)를 찾아내라고 명령해야 합니다. 이때 깊이 우선 탐색(DFS)을 절묘하게 변형한 하이어홀저 알고리즘(Hierholzer's Algorithm)을 사용하면 시간 복잡도 O(V+E)의 선형 시간 만에 경로를 완벽하게 추출해 낼 수 있습니다.
2-1. 간선을 지우며 전진, 막히면 스택에 기록 (Post-order)
단순한 DFS는 막다른 길에 잘못 들어서면 아직 안 간 간선이 남아있는데도 탐색이 종료되어 버리는 치명적인 버그가 발생합니다. 하이어홀저 알고리즘은 이를 '후위 순회(Post-order)' 방식의 스택(Stack)을 통해 천재적으로 해결합니다.
- 출발점(홀수점이 2개라면 그중 하나, 없다면 임의의 정점)에서 DFS 함수를 시작합니다.
- 현재 정점에 연결된 간선 중 하나를 선택해 반대편 정점으로 넘어가고, 방금 지나온 그 간선은 그래프에서 아예 삭제(또는 방문 처리)해 버립니다.
- 이 과정을 반복하여 끝없이 전진하다 보면, 언젠가 연결된 간선이 하나도 남지 않은 '막다른 정점(Dead End)'에 반드시 갇히게 됩니다.
- 여기서가 알고리즘의 핵심입니다! 더 이상 갈 곳이 없어 DFS 함수가 종료(Return)될 때, 비로소 그 정점의 번호를 결과 배열(또는 스택)에 기록합니다. 그리고 이전 정점으로 되돌아가서 남아있는 다른 간선이 있는지 탐색을 재개합니다.
- 모든 탐색이 끝나면 결과 배열에는 정점들이 역순으로 쌓여있게 됩니다. 이 배열을 통째로 뒤집어주면(Reverse) 완벽한 오일러 경로가 탄생합니다. 막힌 길부터 먼저 쌓아두고 메인 경로를 나중에 덮어씌우는 놀라운 발상입니다.
1. 오일러 경로(Eulerian Path)는 그래프의 모든 간선을 단 한 번씩만 통과하는 경로를 의미하며, 흔히 '한붓그리기'로 알려져 있습니다.
2. 무방향 그래프에서 연결된 선이 홀수 개인 홀수점의 개수가 정확히 0개(회로) 또는 2개(경로)일 때만 수학적으로 성립합니다.
3. DFS를 기반으로 간선을 지우며 전진하다가, 더 갈 곳이 없는 막다른 노드부터 역순으로 스택에 쌓아 올려 경로를 추출하는 하이어홀저 알고리즘을 통해 O(V+E)에 구현합니다.