최단 경로 & 슬라이딩 퍼즐 핵심 요약

0. Interactive Demo

0.1 Dijkstra Step-by-Step

아래 6개 노드 가중 그래프에서 다익스트라 알고리즘이 어떻게 최단 경로를 확정해 나가는지 단계별로 확인한다.

그래프 구조: S→A(4), S→B(2), B→A(1), B→C(5), A→C(1), A→D(3), C→D(2)

1. 최단 경로 문제 (SSSP)

1.1 문제 정의

• 입력: 가중 방향 그래프 $G = (V, E)$, 출발 정점 $s \in V$, 간선 가중치 함수 $w: E \rightarrow \mathbb{R}$
• 출력: $s$에서 모든 정점까지의 최소 비용 경로

최단 경로 가중치 정의:

$$\delta(u, v) = \begin{cases} \min{w(p) \mid p \text{는 } u \to v \text{ 경로}} & \text{경로 존재 시} \ \infty & \text{경로 없을 시} \end{cases}$$

1.2 Relaxation 연산

각 정점 $v$는 두 가지 속성을 유지한다:

• v.d : $s$에서 $v$까지 현재까지 알려진 최단 거리 추정값
• v.π : 현재 최단 경로에서 $v$의 선행 정점

RELAX(u, v, w):
    if v.d > u.d + w(u, v):
        v.d = u.d + w(u, v)
        v.π = u

핵심: “u를 경유하면 v까지 더 짧게 갈 수 있는가?” 를 확인하고 가능하면 갱신

1.3 초기화 및 불변 조건

s.d = 0,  v.d = ∞  (v ≠ s)
v.π = NIL  (모든 v)

불변 조건: 항상 $v.d \geq \delta(s, v)$ 성립 → Relaxation 반복으로 $\delta(s, v)$에 수렴

2. 다익스트라 알고리즘

2.1 그리디 전략과 집합 S

1. 최단 경로가 확정된 정점들의 집합 $S$ 유지
2. 매 단계마다 $V - S$에서 d값이 최소인 정점 $u$ 선택
3. $u$를 $S$에 추가하고, $u$에서 나가는 모든 간선 Relaxation

그리디가 성립하는 이유: $w \geq 0$ 이면 이미 확정된 거리는 절대 더 짧아지지 않음

2.2 Min-Priority Queue

2.3 의사 코드

DIJKSTRA(G, w, s):
    s.d = 0,  v.d = ∞  for all v ≠ s
    PQ = V

    while PQ ≠ ∅:
        u = EXTRACT-MIN(PQ)
        for each v ∈ Adj[u]:
            RELAX(u, v, w)

2.4 정확성 증명 (귀류법)

• 가정: $u.d > \delta(s, u)$ 인 정점 $u$가 존재한다고 가정
• 최단 경로 위 첫 미확정 정점 $y$, 선행자 $x \in S$ 설정
• $(x, y)$ Relaxation 완료 → $y.d \leq \delta(s, y)$
• $w \geq 0$ → $\delta(s, y) \leq \delta(s, u) < u.d$
• $\therefore y.d < u.d$ → $u$가 최솟값이라는 조건에 모순!
• $\therefore u.d = \delta(s, u)$ 성립 ✅

2.5 시간 복잡도

$$T(n, m) = O((n+m)\log m) = O(m \log n)$$

$n + m = O(m)$ 인 이유: 연결 그래프에서 $m \geq n-1$ 이므로 $n = O(m)$

2.6 Lazy Deletion (heapq 구현)

from heapq import heappush, heappop

def dijkstra(graph, source):
    dist, parent = init_single_source(graph, source)
    PQ = [(0, source)]
    visited = set()

    while PQ:
        d, u = heappop(PQ)
        if u in visited:   # Lazy Deletion: 낡은 항목 버림
            continue
        visited.add(u)
        for v, w in graph[u]:
            if relax(u, v, w, dist, parent):
                heappush(PQ, (dist[v], v))  # 중복 삽입

    return dist, parent

핵심: heapq는 DECREASE-KEY가 없어서 중복 삽입 후 꺼낼 때 visited로 걸러냄

3. 벨만-포드 알고리즘

3.1 왜 다익스트라가 실패하는가

음수 간선이 있으면 이미 확정한 정점의 거리가 나중에 더 짧아질 수 있음 → 그리디 붕괴

s --(4)--> A
|          ↑
└--(2)--> B --(-5)--> A

Dijkstra: dist[A] = 4  (오답)
실제 최단: dist[A] = 2 + (-5) = -3

3.2 DP 전략

벨만-포드는 동적 프로그래밍 기반:

$$\text{dist}^{(i)}[v] = \min_{(u,v) \in E}\left(\text{dist}^{(i-1)}[u] + w(u,v)\right)$$

$i$번 반복 후 → 최대 $i$개의 간선을 사용하는 최단 경로 확정

3.3 $|V|-1$번 반복하는 이유

• 최단 경로는 사이클을 포함하지 않음 → 최대 $n-1$개의 간선
• $n-1$번 반복이면 모든 최단 경로 확정 보장

BELLMAN-FORD(G, w, s):
    dist[s] = 0,  dist[v] = ∞  for all v ≠ s

    for i from 1 to |V|-1:
        for each edge (u, v) ∈ E:
            RELAX(u, v)

3.4 음수 사이클 탐지

$n$번째 반복에서도 갱신이 발생하면 → 음수 사이클 존재

for each edge (u, v, w):
    if dist[v] > dist[u] + w:
        return "음수 사이클 존재!"

3.5 시간 복잡도

$$T = O(VE) = O(nm)$$

4. 슬라이딩 퍼즐

4.1 반전(Inversion)의 정의

순열에서 $i < j$ 이고 $a_i > a_j$ 인 쌍 $(a_i, a_j)$, 빈 칸(0)은 무시

예시: 1 2 3 4 5 8 0 7 6 → 반전 쌍: (8,7), (8,6), (7,6) → 반전 수 = 3

4.2 홀수 너비 퍼즐 (3×3, 5×5)

• 수직/수평 이동 모두 반전의 홀짝성 보존
• 수직 이동 시 넘는 타일 수 = $n - 1$ = 짝수 → 홀짝성 유지

$$\text{풀이 가능} \iff I \equiv 0 \pmod{2}$$

4.3 짝수 너비 퍼즐 (4×4, 6×6)

• 수직 이동 시 넘는 타일 수 = $n - 1$ = 홀수 → 홀짝성 반전
• $I$와 $R$이 동시에 홀짝성이 바뀌어 $I + R$은 불변

$$\text{풀이 가능} \iff I + R \equiv 1 \pmod{2}$$

4.4 수직 이동이 홀짝성을 바꾸는 이유

4×4에서 수직 이동을 1차원으로 펼치면:

before: [0]  13  14  15  12
after:   13   14  15  [0]  12

12가 15, 14, 13을 하나씩 넘어감
= 인접 교환 3번 (홀수!)
→ 반전 수의 홀짝성 반전

5. BFS (브루트포스 탐색)

5.1 상태를 문자열로 표현

# n=4 목표 상태
target = "123456789ABCDEF0"
# 10 이상은 A,B,C... 로 표현 (한 글자 유지)

5.2 BFS 구현

def bfs(n, start):
    target = "123456789ABCDEF"[:n*n-1] + "0"
    queue = deque([(start, 0)])
    visited = set([start])

    while queue:
        state, depth = queue.popleft()
        if state == target:
            return depth
        blank = state.index('0')
        for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]:
            new_state = move(state, blank, di, dj, n)
            if new_state and new_state not in visited:
                queue.append((new_state, depth+1))
                visited.add(new_state)
    return -1

5.3 3×3은 가능, 4×4는 불가능한 이유

4×4 이상은 A* 알고리즘 필요

6. A* 알고리즘

6.1 $f(n) = g(n) + h(n)$

if new_state not in g or new_depth < g[new_state]:
    g[new_state] = new_depth
    new_f = g[new_state] + h(n, new_state)
    heappush(PQ, (new_f, new_depth, new_state))

6.2 맨해튼 거리 휴리스틱

$$h_{Manhattan}(n) = \sum_{\text{모든 타일}} |\Delta row| + |\Delta col|$$

def h(n, state):
    total = 0
    for i, tile in enumerate(state):
        if tile == '0': continue
        cur_row, cur_col = i // n, i % n
        goal = int(tile, base=16) - 1
        goal_row, goal_col = goal // n, goal % n
        total += abs(cur_row - goal_row) + abs(cur_col - goal_col)
    return total

6.3 Admissibility란?

휴리스틱이 실제 비용을 절대 과대평가하지 않는 조건

$$\boxed{h(n) \leq h^*(n) \quad \text{for all } n}$$

• 과소평가 또는 정확 → Admissible ✅
• 과대평가 → Not Admissible ❌

6.4 Admissibility가 최적해를 보장하는 이유

$f(n)$은 하한(Lower Bound):

$$f(n) = g(n) + h(n) \leq g(n) + h^*(n) = \text{실제 최적 비용}$$

맨해튼 거리가 Admissible인 이유:

• 이동 1번 → 타일 하나가 정확히 1칸 이동
• 이동 1번 → 맨해튼 거리 최대 1 감소
• $h(n)$만큼 이동해야 목표 도달 → $h_{Manhattan}(n) \leq h^*(n)$ ✅

결론: $$h \text{ Admissible} \implies f(n) \text{이 하한} \implies \text{PQ에서 처음 꺼낸 목표 = 최적해}$$

6.5 BFS vs A* 비교

7. 핵심 질문 Q&A 모음

7.1 heapq == PQ?

A. 같은 개념이지만 다른 레벨

• PQ = 추상 자료구조 (개념)
• heapq = 파이썬에서 이진 최소 힙으로 PQ를 구현한 라이브러리

Priority Queue (추상 개념)
        ↓ 구현
heapq (이진 최소 힙)

단, heapq에는 DECREASE-KEY가 없어서 다익스트라에서 Lazy Deletion으로 우회해야 함

7.2 heap에 노드가 한 번만 들어가나?

A. 아니다. 같은 노드가 여러 번 들어갈 수 있다.

# Relaxation 성공할 때마다 무조건 새 항목 삽입
heappush(PQ, (dist[v], v))  # 기존 항목 삭제 없이 추가!

• DECREASE-KEY가 없으므로 기존 항목은 그대로 두고 새 항목 추가
• PQ 최대 크기 = $O(m)$ (간선 수만큼 쌓임)
• 꺼낼 때 visited 체크로 낡은 항목 버림

7.3 $n + m = O(m)$ 인 이유?

A. 연결 그래프에서 $m \geq n - 1$ 이기 때문

연결 그래프 조건: 정점 n개 연결 → 최소 n-1개 간선 필요
→ m ≥ n-1
→ n = O(m)
→ n + m = O(m) + O(m) = O(m)

비연결 그래프라면 성립 안 하지만, 다익스트라는 연결 그래프를 가정

7.4 벨만-포드는 그리디인가 DP인가?

A. DP다.

점화식: $\text{dist}^{(i)}[v] = \min(\text{dist}^{(i-1)}[u] + w(u,v))$ → DP의 전형적 구조

7.5 Reachable이 어디 reachable?

A. 목표 상태(Goal State)에 도달 가능하다는 의미

목표 상태:           초기 상태:
┌─────────┐         ┌─────────┐
│ 1  2  3 │         │ 1  2  3 │
│ 4  5  6 │   ←?    │ 4  5  6 │
│ 7  8  0 │         │ 8  7  0 │
└─────────┘         └─────────┘
 
"합법적인 이동(상하좌우)만으로 목표 상태까지 갈 수 있는가?"

반전 수로 판별 가능 → 실제로 탐색하지 않아도 $O(n^2)$에 판별

7.6 4×4에서 수직 이동이 홀짝성을 바꾸는 이유?

A. 수직 이동 = 1차원으로 펼치면 인접 교환 3번(홀수)

before: [0]  13  14  15  12
after:   13   14  15  [0]  12
 
12가 이동하면서 13, 14, 15를 하나씩 넘어감
= 인접 교환 3번
→ 반전 수 N → N+3 (홀짝성 반전!)

7.7 $R$을 더하는 이유?

A. 수직 이동 시 $I$와 $R$이 동시에 홀짝성이 바뀌어 서로 상쇄되기 때문

수직 이동 1번:
  I: 홀짝 바뀜 (+3)
  R: 홀짝 바뀜 (±1)
  ──────────────
  I+R: 홀짝 유지! (불변량)
 
목표 상태: I=0, R=1 → I+R = 1
∴ 풀이 가능 ⟺ I+R ≡ 1 (mod 2)

7.8 BFS가 브루트포스인가?

A. 맞다. BFS = 브루트포스

• 어떤 휴리스틱 없이 가능한 모든 상태를 빠짐없이 탐색
• 3×3: $9! = 362,880$개 → 가능
• 4×4: $16! \approx 2 \times 10^{13}$개 → 불가능 → A* 필요

7.9 선형 탐색 다익스트라는 PQ를 안 쓰나?

A. 맞다. PQ 대신 배열을 선형 탐색으로 최솟값을 찾는 방식

# PQ 없이 매번 전체 배열 순회
u = 미방문 노드 중 dist가 최소인 노드  # O(V)

밀집 그래프($m \approx n^2$)에서는 오히려 선형 탐색이 유리

7.10 Lazy Deletion이 뭔가?

A. 지우지 않고 넣어두고, 꺼낼 때 버리는 방식

문제: heapq는 DECREASE-KEY가 없음
해결: 기존 항목 삭제 대신 새 항목 추가 (중복 삽입)
 
PQ: [(3, A), (7, A)]  ← (7,A)는 낡은 항목
       ↓
(3, A) 꺼냄 → 처리 ✅
(7, A) 꺼냄 → visited 체크 → 버림 ❌

Dijkstra에서는 visited로, A*에서는 g 값 비교로 걸러냄

7.11 A* 코드가 Lazy Deletion인가?

A. 엄밀히는 다르다

A*는 Lazy Deletion보다 “더 짧은 경로만 조건부 삽입” 에 가까움

7.12 “길고 짧다"는 게 무슨 뜻인가?

A. 슬라이딩 퍼즐에서 “거리” = 이동 횟수

같은 상태 X에 도달하는 두 경로:
  경로 A: 3번 이동  ← 더 짧음
  경로 B: 7번 이동  ← 더 김
 
new_depth < g[new_state]
= "지금 발견한 경로의 이동 횟수가 기존보다 적다"

7.13 goal = int(tile, base=16) - 1 이 좌표인가?

A. 아니다. 1차원 인덱스이고, 좌표로 변환해야 맨해튼 거리 계산 가능

goal     = int(tile, base=16) - 1   # 1차원 인덱스
goal_row = goal // n                 # 2차원 행 좌표
goal_col = goal % n                  # 2차원 열 좌표
 
# 맨해튼 거리
dist = abs(cur_row - goal_row) + abs(cur_col - goal_col)

n=4, tile="A" (10번 타일):
goal = 9
goal_row = 9 // 4 = 2
goal_col = 9 %  4 = 1
→ 목표 위치: (2행, 1열) ✅

7.14 Admissibility가 왜 중요한가? (쉽게)

A. 낙관적으로 추정해야 최적 경로를 안 놓친다

실제 거리 = 10
 
h(n) = 7  → 낙관적 추정 ✅ → 이 경로 계속 탐색
h(n) = 13 → 비관적 추정 ❌ → 이 경로 포기 → 최적해 놓침!

Admissible → $f(n)$이 항상 하한 → 최적 경로를 절대 건너뛰지 않음 → PQ에서 목표를 처음 꺼내는 순간 = 최적해