오일러 경로/회로 (Eulerian Path and Circuit)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 3분 · 1,006자/단어 #algorithm #graph #traversal

정의

오일러 경로 (Eulerian Path) 는 그래프의 모든 간선을 정확히 한 번씩 지나는 경로. 오일러 회로 (Eulerian Circuit) 는 시작점과 끝점이 같은 오일러 경로.

Leonhard Euler (1736) 가 Königsberg 다리 문제 (Seven Bridges of Königsberg) 로 처음 연구. 그래프 이론의 탄생.

판정 조건 (무방향 그래프):

오일러 회로: 모든 정점의 차수가 짝수.
오일러 경로: 정확히 두 정점만 홀수 차수 (나머지 모두 짝수).

유방향 그래프는 in-degree = out-degree 조건.

문제 상황과 동기

모든 간선을 정확히 한 번씩 방문하는 경로 찾기.

naive (DFS 완전 탐색): 모든 경로 시도. 간선 E 개 → O(E!) 폭발.
Hierholzer 알고리즘: O(V + E). 한 번의 DFS.

핵심 통찰: 사이클을 찾고, 사이클에서 뻗은 다른 사이클을 병합. 오일러 회로가 존재하는 그래프는 모든 간선이 하나의 큰 사이클로 연결됨.

자주 등장: 경로 복원, DNA 조합, TSP 변형.

시각화

핵심 아이디어

invariant: 오일러 회로 존재 ⇔ 모든 정점 차수 짝수 + 연결 그래프.

Hierholzer 알고리즘 (무방향):

1. 임의 정점 v 에서 DFS, 더 이상 미방문 간선이 없을 때까지 진행 → cycle C.
2. C 의 각 정점에서 미방문 간선이 있으면 재귀 DFS → sub-cycle 병합.
3. 역순으로 path 구성.

스택 기반 구현:

path = []
stack = [start]
while stack:
    v = stack[-1]
    if v has unvisited edge:
        u = next unvisited neighbor
        mark (v, u) visited
        stack.push(u)
    else:
        path.append(stack.pop())
return path.reverse()

알고리즘

무방향 그래프 (Hierholzer)

hierholzer(start):
    stack = [start]
    path = []
    while stack:
        v = stack[-1]
        if adj[v] has unvisited edge (v, u):
            mark (v, u) visited
            stack.push(u)
        else:
            path.append(stack.pop())
    return reversed(path)

유방향 그래프

동일하지만, 간선 방향 체크. in-degree = out-degree 조건.

판정 조건

has_eulerian_circuit(G):
    return all(degree(v) % 2 == 0) and is_connected(G)

has_eulerian_path(G):
    odd_degree_count = count(v: degree(v) % 2 == 1)
    return odd_degree_count == 0 or odd_degree_count == 2

구현

// 오일러 회로 (Hierholzer, 무방향 그래프, O(V+E))
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m; cin >> n >> m;
  vector<multiset<int>> adj(n);
  vector<int> deg(n, 0);
  for (int i = 0; i < m; i++) {
      int u, v; cin >> u >> v; u--; v--;
      adj[u].insert(v); adj[v].insert(u);
      deg[u]++; deg[v]++;
  }
  // 판정: 모든 차수가 짝수
  for (int d : deg) if (d % 2 != 0) {
      cout << "NO CIRCUIT\n"; return 0;
  }
  // Hierholzer
  vector<int> path;
  stack<int> st; st.push(0);
  while (!st.empty()) {
      int v = st.top();
      if (!adj[v].empty()) {
          int u = *adj[v].begin();
          adj[v].erase(adj[v].find(u));
          adj[u].erase(adj[u].find(v));
          st.push(u);
      } else {
          path.push_back(v);
          st.pop();
      }
  }
  reverse(path.begin(), path.end());
  for (int v : path) cout << v + 1 << " ";
  cout << "\n";
}

# 오일러 회로 (Hierholzer, 무방향 그래프)
import sys
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
adj = defaultdict(list)
deg = [0] * n
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj[u].append(v)
  adj[v].append(u)
  deg[u] += 1; deg[v] += 1

if any(d % 2 != 0 for d in deg):
  print("NO CIRCUIT")
else:
  path = []
  stack = [0]
  while stack:
      v = stack[-1]
      if adj[v]:
          u = adj[v].pop()
          adj[u].remove(v)
          stack.append(u)
      else:
          path.append(stack.pop())
  path.reverse()
  print(' '.join(str(v + 1) for v in path))

// 오일러 회로 (Hierholzer, 무방향 그래프)
import java.util.*;
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      List<Integer>[] adj = new ArrayList[n];
      int[] deg = new int[n];
      for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int v = Integer.parseInt(st.nextToken()) - 1;
          adj[u].add(v); adj[v].add(u);
          deg[u]++; deg[v]++;
      }
      for (int d : deg) if (d % 2 != 0) {
          System.out.println("NO CIRCUIT");
          return;
      }
      List<Integer> path = new ArrayList<>();
      Stack<Integer> stack = new Stack<>();
      stack.push(0);
      while (!stack.isEmpty()) {
          int v = stack.peek();
          if (!adj[v].isEmpty()) {
              int u = adj[v].remove(adj[v].size() - 1);
              adj[u].remove((Integer) v);
              stack.push(u);
          } else {
              path.add(stack.pop());
          }
      }
      Collections.reverse(path);
      StringBuilder sb = new StringBuilder();
      for (int v : path) sb.append(v + 1).append(' ');
      System.out.println(sb);
  }
}

stdin

결과

1 2 3 4 1

복잡도

항목	값
판정	O(V) - 차수 확인
경로 구성	O(V + E) - Hierholzer
전체	O(V + E)
공간	O(V + E) - 인접 리스트 + 스택

각 간선 정확히 한 번 방문. DFS 스택은 최대 V 깊이.

변형 / 활용

1. 유방향 오일러 경로

판정: 모든 정점 in = out. 경로: 한 정점만 out = in + 1 (시작), 한 정점만 in = out + 1 (끝).

2. 중국인 우체부 문제 (Chinese Postman)

오일러 회로가 없는 그래프에서 최소 간선 중복으로 모든 간선 방문. 홀수 차수 정점 쌍 매칭 + 최단 경로.

3. De Bruijn 그래프

k-mer DNA 서열 조합. 오일러 경로로 전체 서열 복원.

함정

1. 연결 그래프 확인 누락

차수 조건만으로 불충분. 간선이 여러 컴포넌트에 흩어지면 오일러 경로 불가능. DFS/BFS 로 연결성 확인.

2. 간선 중복 처리

무방향 그래프에서 같은 (u, v) 간선 여러 개 (multi-edge). multiset 또는 edge ID 관리 필요.

3. 경로 역순

Hierholzer 는 스택 pop 순서가 역순. 최종 reverse() 필수.

4. 유방향 vs 무방향 혼동

유방향은 in/out degree, 무방향은 degree. 조건이 다름.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1199	오일러 회로	-	kokoa-lab
BOJ 1591	수열 복원	-	kokoa-lab
BOJ 16168	퍼레이드	-	kokoa-lab

참고

이 글의 용어 (3개)

깊이 우선 탐색 (DFS)algorithm: 정의 깊이 우선 탐색 (Depth-First Search, DFS) 는 그래프 G=(V, E) 에서 갈 수 있는 만큼 깊이 들어가다가 막히면 백트래킹하는 알고리즘. 스택 (LIF…
graphdata-structure: 개요
Hamiltonian Path: 모든 정점 한 번씩algorithm: 정의 Hamiltonian Path 는 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로. 시작 = 끝이면 Hamiltonian Cycle. 일반 그래프에서 NP-complet…