21. 해밀턴 경로 (Hamiltonian Path) — NP-완전, 백트래킹

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

1. 본질: 해밀턴 경로 (Hamiltonian Path)는 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로로, 존재 판별 자체가 NP-완전 (NP-Complete) 문제다.
2. 가치: Dirac 정리, Ore 정리 등 충분조건으로 존재를 보장할 수 있고, 백트래킹으로 탐색하거나 동적 프로그래밍 (DP + 비트마스크, O(2ⁿn²))으로 TSP와 동일하게 접근한다.
3. 판단 포인트: 오일러 경로(간선 방문, P)와 혼동하지 말 것 — 해밀턴 경로는 정점 방문이며 NP-완전으로 다항식 시간 알고리즘이 알려져 있지 않다.

Ⅰ. 개요 및 필요성

해밀턴 경로 (Hamiltonian Path)는 1857년 윌리엄 해밀턴이 제안한 정다면체 위의 여행 퍼즐에서 유래한다. 해밀턴 회로 (Hamiltonian Circuit)는 모든 정점을 한 번씩 방문하고 시작 정점으로 돌아오는 것이다.

📢 섹션 요약 비유: 해밀턴 경로는 도시들을 한 번씩만 방문하는 여행 경로가 존재하는지 찾는 것이다. 오일러(도로를 한 번씩)와 달리, 정점을 한 번씩 방문하는 조건은 훨씬 어렵다.

Ⅱ. 아키텍처 및 핵심 원리

해밀턴 경로 존재 충분조건

Dirac 정리 (1952): n ≥ 3인 그래프에서 모든 정점의 차수 ≥ n/2이면 해밀턴 회로 존재

Ore 정리 (1960): n ≥ 3인 그래프에서 인접하지 않은 모든 정점 쌍 (u, v)에 대해 deg(u) + deg(v) ≥ n이면 해밀턴 회로 존재

주의: 이 조건들은 충분조건이지 필요조건이 아님
  → 조건 불만족 ≠ 해밀턴 경로 없음
  → 조건 만족 = 해밀턴 경로 반드시 존재

백트래킹 알고리즘

path[0..n-1]: 방문 순서
visited[0..n-1]: 방문 여부

solve(pos):
  if pos == n: 경로 발견!
  for v in 0..n-1:
    if not visited[v] and adj[path[pos-1]][v]:
      path[pos] = v
      visited[v] = true
      if solve(pos+1): return true
      visited[v] = false  // 역추적
  return false

ASCII 다이어그램 — 백트래킹 탐색 트리

┌──────────────────────────────────────────────────────────┐
│  그래프: A─B─C─D (선형)                                  │
│           │   │                                          │
│           └───┘                                          │
│                                                          │
│  백트래킹 탐색 트리 (A에서 시작):                         │
│  A                                                       │
│  ├─ B                                                    │
│  │  ├─ C                                                 │
│  │  │  ├─ D  → 해밀턴 경로: A-B-C-D ✓                   │
│  │  │  └─ (역추적)                                       │
│  │  └─ (역추적)                                          │
│  └─ (역추적)                                             │
│                                                          │
│  최악: n! 탐색 (가지치기 없을 때)                         │
└──────────────────────────────────────────────────────────┘

DP + 비트마스크 (O(2ⁿn²))

dp[mask][v] = mask에 포함된 정점들을 방문하고 현재 v에 있을 때의 최소 비용

dp[1<<s][s] = 0  (시작 정점 s에서 시작)
전이: dp[mask|(1<<v)][v] = min(dp[mask][u] + w(u,v))
     단, v ∉ mask이고 (u,v) 간선 있을 때

최종: dp[(1<<n)-1][*] 중 최솟값 = 최단 해밀턴 경로

📢 섹션 요약 비유: 비트마스크 DP는 "어느 도시를 방문했는지"를 비트로 기록하는 여행 일지다. 20개 도시라면 2²⁰=100만 가지 상태만 기록하면 된다.

Ⅲ. 비교 및 연결

해밀턴 vs 오일러 비교

TSP (외판원 문제)와의 관계

TSP = 최단 가중치 해밀턴 회로 탐색
해밀턴 경로 존재 = TSP의 결정 버전
TSP 최적화 = NP-hard

📢 섹션 요약 비유: 해밀턴 경로 존재 판별 ≤ TSP ≤ NP-hard의 계층 관계를 이해하면, "왜 내비게이션은 최적 경로를 즉시 못 찾나?"의 이론적 이유가 명확해진다.

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

실무 시나리오

시나리오 1: 게놈 서열 조립 (Genome Assembly)

• DNA 조각들(reads)을 겹침 그래프에서 해밀턴 경로로 재조합
• 실용적 접근: De Bruijn 그래프 + Euler Path (정점 → 간선 변환)

시나리오 2: 파레트 포장 순서 (물류)

• 여러 창고를 한 번씩 방문하는 트럭 경로
• n=15 이하: DP 비트마스크 O(2¹⁵×15²) ≈ 7백만 → 실시간 가능

시나리오 3: 집적회로 테스트 경로

• 칩의 모든 핀을 한 번씩 테스트하는 탐침 순서
• 소규모 핀 배열(n≤20)에 DP 비트마스크 적용

기술사 판단 포인트

📢 섹션 요약 비유: 해밀턴 경로는 퍼즐처럼 어렵다. 30개 도시만 되어도 완전 탐색이 우주 나이보다 오래 걸린다. 그래서 현실에서는 "충분히 좋은" 근사 해법을 사용한다.

Ⅴ. 기대효과 및 결론

해밀턴 경로 (Hamiltonian Path)는 NP-완전 문제로 효율적인 일반 알고리즘이 존재하지 않는다. 소규모에서는 DP + 비트마스크, 대규모에서는 근사 알고리즘이나 메타휴리스틱을 사용한다. Dirac/Ore 정리는 존재 보장에 활용한다.

핵심 결론: 해밀턴 경로는 P≠NP 가설에 의해 다항식 시간 알고리즘이 존재하지 않을 것으로 믿어지는 문제다. 현실 시스템에서는 근사와 휴리스틱이 실용적 해법이다.

📢 섹션 요약 비유: 해밀턴 경로는 "모든 도시를 한 번씩 방문하는 완벽한 여행 계획"이다. 완벽한 답을 구하려면 지수적 시간이 걸리고, 현실에서는 "아주 좋지만 완벽하지 않은" 경로로 타협한다.

📌 관련 개념 맵

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

[그래프 완전 탐색 (DFS/BFS — 다항식 P)]
    │
    ▼
[해밀턴 경로 (Hamiltonian Path — NP-완전)]
    │
    ▼
[외판원 문제 (TSP — 해밀턴 회로의 최적화 버전)]
    │
    ▼
[DP + 비트마스크 (소규모 n≤20 정확해 O(2ⁿn²))]
    │
    ▼
[메타휴리스틱 (대규모 근사해 — 유전 알고리즘·모의담금질)]

해밀턴 경로는 P≠NP 가설에 의해 다항식 해가 없는 NP-완전 문제로, 소규모에서 DP+비트마스크, 대규모에서 메타휴리스틱 근사가 실용적 해법이다.

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

1. 🏙️ 해밀턴 경로는 모든 도시를 딱 한 번씩만 방문하는 여행 코스를 찾는 것인데, 이 코스가 존재하는지 확인하는 것조차 매우 어렵다.
2. 🧩 도시가 20개만 넘어도 가능한 경우의 수가 우주의 원자 수보다 많아질 수 있어서, 컴퓨터도 완벽한 답을 빠르게 찾지 못한다.
3. 🔍 그래서 실제로는 "완벽하지 않아도 충분히 좋은" 경로를 빠르게 찾는 근사 방법을 사용한다.