Hierholzer 알고리즘: 오일러 경로/회로

오일러 경로란

그래프의 모든 간선을 정확히 한 번씩 지나는 경로다. 모든 노드를 방문하는 해밀턴 경로와 다르다.

	오일러 (Euler)	해밀턴 (Hamilton)
대상	간선	노드
복잡도	O(E)	NP-complete

존재 조건

• 오일러 회로 (시작 = 끝): 모든 노드의 진입 차수 = 진출 차수
• 오일러 경로 (시작 ≠ 끝): 정확히 하나의 노드에서 진출 차수 = 진입 차수 + 1 (시작점), 정확히 하나의 노드에서 진입 차수 = 진출 차수 + 1 (끝점), 나머지는 동일

무방향 그래프에서는 홀수 차수 노드가 0개(회로) 또는 2개(경로)일 때 존재한다.

---

Hierholzer 알고리즘

핵심 아이디어

DFS로 간선을 소모하면서 탐색하되, 후위 순서로 기록한 뒤 뒤집는다.

후위 기록이 필요한 이유: 막다른 길(간선이 먼저 소진되는 분기)이 경로 뒤쪽에 배치되어야 전체 경로가 끊기지 않는다. 전위 기록하면 막다른 분기를 먼저 방문했을 때 나머지 간선을 사용할 수 없게 된다.

동작 예시

그래프: A→B, A→C, B→C, C→A

dfs(A)
  간선 A→B 소모, dfs(B)
    간선 B→C 소모, dfs(C)
      간선 C→A 소모, dfs(A)
        간선 A→C 소모, dfs(C)
          간선 없음 → route에 C 추가
        route에 A 추가
      route에 C 추가
    route에 B 추가
  route에 A 추가

route: [C, A, C, B, A]
뒤집기: [A, B, C, A, C]  ← 올바른 오일러 경로

코드

#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

map<string, multiset<string>> graph;
vector<string> route;

void dfs(const string& node) {
    while (!graph[node].empty()) {
        string next = *graph[node].begin();
        graph[node].erase(graph[node].begin());
        dfs(next);
    }
    route.push_back(node);
}

// 사용: dfs(시작점), reverse(route), route가 오일러 경로

비재귀 버전

재귀 깊이가 간선 수만큼 될 수 있다. 스택 오버플로우가 우려되면 명시적 스택을 쓴다.

void hierholzer(const string& start) {
    stack<string> stk;
    stk.push(start);

    while (!stk.empty()) {
        string cur = stk.top();
        if (!graph[cur].empty()) {
            string next = *graph[cur].begin();
            graph[cur].erase(graph[cur].begin());
            stk.push(next);
        } else {
            route.push_back(cur);
            stk.pop();
        }
    }
    reverse(route.begin(), route.end());
}

---

메모

• multiset을 쓰는 이유
  • 같은 목적지로의 간선이 여러 개일 수 있다 (멀티그래프). set은 중복을 제거하므로 multiset을 쓴다
  • begin()이 항상 정렬 순서상 최소이므로, 알파벳 순서가 필요한 문제에서 자동으로 사전순 경로가 된다
  • erase(begin())으로 간선을 소모한다
• 후위 기록 vs 전위 기록
  • 전위 기록(진입 시 push)하면 분기점에서 막다른 길을 먼저 방문했을 때 경로가 끊긴다
  • 후위 기록(간선 소진 후 push)하면 막다른 길이 결과의 뒤쪽에 배치되어 경로가 올바르게 이어진다
• 적용 사례
  • 프로그래머스 43164 여행경로: 항공권을 모두 사용하는 경로

복잡도

	시간	공간
Hierholzer	O(E log E)	O(E)

multiset 삽입이 O(log E)이므로 전체 O(E log E). unordered_map + vector + 정렬로 구현하면 O(E log E)는 동일하다.