20. 오일러 경로/회로 (Euler Path/Circuit) — Fleury / Hierholzer

핵심 인사이트 (3줄 요약)

1. 본질: 오일러 경로 (Euler Path)는 그래프의 모든 간선을 정확히 한 번씩 방문하는 경로이며, 오일러 회로 (Euler Circuit)는 시작 정점으로 돌아오는 오일러 경로다.
2. 가치: 오일러 회로의 존재 조건(모든 정점 짝수 차수)은 판별이 O(V)이고, Hierholzer 알고리즘으로 O(E)에 실제 경로를 구성하여 한붓그리기, 우편 배달 문제, 회로 설계 등에 활용된다.
3. 판단 포인트: 오일러(간선 모두 방문)와 해밀턴(정점 모두 방문)을 혼동하지 말 것 — 오일러는 다항식 시간, 해밀턴은 NP-완전이다.

Ⅰ. 개요 및 필요성

오일러 경로/회로 문제는 1736년 쾨니히스베르크 다리 문제로 시작된 그래프 이론의 기원이다. "7개의 다리를 각각 한 번씩만 건너서 모두 건널 수 있는가?"라는 문제를 오일러가 그래프로 모델링하여 해결했다.

존재 조건

무방향 그래프:

• Euler Circuit: 모든 정점의 차수가 짝수 + 연결 그래프
• Euler Path: 홀수 차수 정점이 정확히 2개 (시작, 종료) + 연결

방향 그래프:

• Euler Circuit: 모든 정점에서 in-degree = out-degree
• Euler Path: 정확히 1개 정점에서 out-degree = in-degree + 1 (시작), 1개에서 in-degree = out-degree + 1 (종료)

📢 섹션 요약 비유: 오일러 회로는 한붓그리기다. 손을 종이에서 떼지 않고 모든 선을 정확히 한 번씩 그리는 것이 가능한지를 판단한다.

Ⅱ. 아키텍처 및 핵심 원리

존재 조건 판별 예시

그래프 A:              그래프 B:
A─B─C─D               A─B─C
│   │                 │   │
└───┘                 └───┘
차수: A=2,B=2,C=2,D=2  차수: A=2,B=3,C=3 → 홀수 2개
→ Euler Circuit 가능   → Euler Path만 가능 (B→C 또는 C→B)

Hierholzer 알고리즘 (O(E))

1. 임의 정점에서 DFS (막다른 곳까지)
2. 막다른 곳에 도달하면 스택에 Push
3. 역추적하며 미방문 간선이 있으면 다시 DFS
4. 스택 역순 = Euler Circuit/Path

ASCII 다이어그램 — Hierholzer 동작

┌──────────────────────────────────────────────────────────┐
│  그래프:  A─B─C─D                                        │
│           │   │                                          │
│           └───┘                                          │
│                                                          │
│  Hierholzer 진행 (A에서 시작):                            │
│  DFS: A→B→C→A (사이클, 막힘) → 스택: [A]                 │
│  역추적: C→D→B 방문 가능 → C에서 DFS                     │
│  DFS: C→D→B→C (완성) → 스택: [A, C, B, D, C]             │
│  역추적: B에서 A→B 사용 → 스택: [A, C, B, D, C, B, A]    │
│                                                          │
│  역순 출력: A→B→C→D→B→C→A (Euler Circuit)                │
└──────────────────────────────────────────────────────────┘

Fleury 알고리즘 vs Hierholzer

Fleury는 간선 방문 시 "이 간선이 교량인가?"를 O(E) 검사하므로 전체 O(E²). Hierholzer는 스택 기반으로 O(E)에 처리.

📢 섹션 요약 비유: Hierholzer는 미로에서 막힌 곳에 도달할 때마다 표시해두고, 나중에 표시된 순서를 뒤집으면 경로가 완성되는 방식이다.

Ⅲ. 비교 및 연결

오일러 vs 해밀턴

중국 우편 배달부 문제 (Chinese Postman Problem)

모든 간선을 적어도 한 번 방문하는 최단 경로:

• 그래프에 Euler Circuit이 있으면 그것이 최적
• 없으면 홀수 차수 정점 간 최단 경로 추가로 Euler Circuit 생성

📢 섹션 요약 비유: 오일러 경로는 우편배달부가 모든 골목을 한 번씩만 지나가는 최적 배달 루트 문제다. 모든 골목이 짝수 방향으로 연결되어 있으면 최적 루트가 존재한다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1: 도로 청소차 루트 최적화

• 모든 도로를 최소 이동으로 청소
• Euler Circuit = 모든 도로를 각 1회 청소하는 최적 루트
• 홀수 차수 교차로 처리: 최소 추가 이동 계산

시나리오 2: 회로 기판 테스트 경로

• PCB 보드의 모든 연결선을 한 번씩 테스트하는 탐침 경로
• Euler Path로 테스트 탐침 이동 최소화

시나리오 3: DNA 서열 재조합 (생물정보학)

• De Bruijn 그래프: k-mer 시퀀스를 간선으로 표현
• Euler Path = DNA 서열 재구성
• 차세대 시퀀싱 (NGS) 알고리즘의 핵심

기술사 판단 포인트

📢 섹션 요약 비유: 오일러 경로는 지도의 모든 도로를 정확히 한 번씩 주행하는 택배 루트와 같다. 교차로(정점)는 여러 번 지나도 되지만, 도로(간선)는 딱 한 번씩만 사용한다.

Ⅴ. 기대효과 및 결론

오일러 경로/회로는 간선 방문 완전성을 O(V) 판별 + O(E) 구성으로 효율적으로 해결한다. Hierholzer 알고리즘은 O(E) 시간으로 Fleury보다 월등히 빠르며, DNA 서열 재구성, 우편 배달, 회로 테스트 등 실세계 문제에 직접 적용된다.

핵심 결론: "모든 간선을 한 번씩"이라는 조건은 차수 하나만 확인하면 O(V)에 판별된다. 그래프 이론이 복잡한 현실 문제를 단순한 수학적 조건으로 환원하는 대표 사례다.

📢 섹션 요약 비유: 오일러 경로는 손을 떼지 않고 그림 그리기의 수학적 버전이다. 가능 여부는 교차점마다 선의 수를 세는 것만으로 즉시 알 수 있다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[그래프(Graph) 탐색 기초 — 정점(V)과 간선(E) 구조]
    │
    ▼
[오일러 경로 조건 — 홀수 차수 정점 0개 또는 2개]
    │
    ▼
[오일러 서킷 (Eulerian Circuit) — 모든 간선을 1회 순회 후 시작점 복귀]
    │
    ▼
[플뢰리 알고리즘 / Hierholzer 알고리즘 — O(E) 탐색 구현]
    │
    ▼
[해밀턴 경로 — 오일러 경로와 대비, 모든 정점을 1회 방문 (NP-완전)]

오일러 경로는 간선을 기준으로 홀수 차수 조건을 검사하며, 플뢰리/Hierholzer 알고리즘으로 O(E) 내에 탐색이 가능하다.

👶 어린이를 위한 3줄 비유 설명

1. ✏️ 오일러 경로는 손을 종이에서 떼지 않고 모든 선을 한 번씩만 그리는 "한붓그리기"가 가능한지 찾는 것이다.
2. 🔢 비법은 간단하다: 교차점마다 만나는 선의 수가 모두 짝수이면 출발점으로 돌아오는 한붓그리기가 가능하다.
3. 🧬 DNA 서열 퍼즐에서도 이 원리가 사용된다 — 작은 DNA 조각들을 연결해 전체 서열을 복원하는 데 오일러 경로를 활용한다.