> [!abstract] Introduction > Uniform-Cost Search(균일 비용 탐색, UCS)는 시작 노드에서의 실제 경로 비용 $g(n)$이 가장 작은 노드부터 확장하는 그래프 탐색 알고리즘입니다. 간선 비용이 모두 같을 때는 [[Breadth-First Search]]와 동일하게 동작하지만, 간선 비용이 서로 다를 때도 최적 해를 보장합니다. [[Best-First Search]] 프레임워크에서 $f(n) = g(n)$으로 설정한 특수한 경우이며, Dijkstra 알고리즘의 그래프 탐색 버전에 해당합니다. 이 글에서는 BFS의 한계에서 출발하여 UCS의 동작 원리, 시간·공간 복잡도, 그리고 Dijkstra 알고리즘과의 관계를 살펴봅니다. ## BFS의 한계와 UCS의 필요성 [[Breadth-First Search]]는 얕은 깊이의 노드부터 차례대로 확장한다. 이 전략은 **모든 간선의 비용이 동일할 때**는 최적이지만, 간선 비용이 다르면 문제가 생긴다. BFS는 "몇 번 이동했는가"만 보지, "얼마나 비용을 썼는가"는 보지 않기 때문이다. ![[ucsVsBfs.svg]] 예를 들어, 출발지에서 목적지까지 고속도로(비용 1)와 국도(비용 5)가 있다면, BFS는 둘 다 "한 번 이동"으로 취급하여 국도를 선택할 수 있다. UCS는 누적 비용 $g(n)$을 기준으로 하므로 고속도로를 먼저 탐색한다. ## 알고리즘 동작 원리 UCS는 [[Best-First Search]]에 $f(n) = g(n)$을 넘긴 것과 같다. AIMA (Russell & Norvig, 2021)에서는 단 한 줄로 정의한다[^aima-ucs]. ``` function UNIFORM-COST-SEARCH(problem) returns solution or failure return BEST-FIRST-SEARCH(problem, PATH-COST) ``` 내부 동작을 풀어쓰면 다음과 같다. 1. 시작 노드를 [[Priority Queue]]에 삽입한다. 키는 $g = 0$이다. 2. 큐에서 $g(n)$이 가장 작은 노드를 꺼낸다. 3. 꺼낸 노드가 목표이면 경로를 반환한다. 4. 그렇지 않으면 인접 노드 각각에 대해 $g(\text{neighbor}) = g(n) + c(n, \text{neighbor})$를 계산한다. 5. 아직 방문하지 않았거나, 기존보다 더 짧은 경로를 발견했으면 큐에 삽입(또는 갱신)한다. 6. 큐가 빌 때까지 반복한다. 핵심은 **노드를 큐에서 꺼내는 시점**에 그 노드까지의 최단 비용이 확정된다는 것이다. 이미 확장된 노드는 다시 처리하지 않아도 된다 — 비용이 음수가 아닌 한, 나중에 더 싼 경로로 도달하는 것은 불가능하기 때문이다. ## 탐색 예시 아래 가중 그래프에서 S에서 G까지의 최단 경로를 UCS로 찾는 과정을 보자. ![[ucsGraphExample.svg]] **Step 1** — S를 확장한다 ($g = 0$). 인접한 A ($g = 1$)와 B ($g = 4$)가 큐에 들어간다. **Step 2** — 큐에서 $g$가 가장 작은 A ($g = 1$)를 꺼내 확장한다. C ($g = 1 + 5 = 6$)와 D ($g = 1 + 8 = 9$)가 큐에 들어간다. **Step 3** — B ($g = 4$)를 확장한다. D까지의 새 경로 비용이 $4 + 1 = 5$로, 기존 경로($g = 9$)보다 저렴하므로 D의 $g$를 5로 갱신한다. **Step 4** — D ($g = 5$)를 확장한다. G ($g = 5 + 3 = 8$)가 큐에 들어간다. **Step 5** — C ($g = 6$)를 확장한다. G까지의 새 경로 비용이 $6 + 1 = 7$로, 기존 경로($g = 8$)보다 저렴하므로 G의 $g$를 7로 갱신한다. **Step 6** — G ($g = 7$)를 꺼낸다. 목표 노드이므로 탐색 종료. 최적 경로는 S → A → C → G (비용 7)이다. 이 과정에서 주목할 점은 두 가지다. Step 3에서는 B를 경유하는 경로가 D에 더 저렴하게 도달하여 $g$가 9에서 5로 갱신되었고, Step 5에서는 C를 경유하는 경로가 G에 더 저렴하게 도달하여 $g$가 8에서 7로 갱신되었다. UCS는 이처럼 매 단계마다 최소 비용 노드를 확장하면서 더 저렴한 경로를 발견하면 즉시 갱신하기 때문에, 여러 경로 중 실제로 가장 저렴한 것을 올바르게 선택한다. ## Python 구현 ```python import heapq from typing import Optional def ucs( graph: dict[str, list[tuple[str, int]]], start: str, goal: str, ) -> Optional[tuple[int, list[str]]]: """Uniform-Cost Search. Args: graph: 인접 리스트. {노드: [(이웃, 비용), ...]}. start: 시작 노드. goal: 목표 노드. Returns: (최소 비용, 경로 리스트) 또는 경로 없으면 None. """ # (g값, 삽입순서, 노드) counter = 0 frontier = [(0, counter, start)] came_from: dict[str, Optional[str]] = {start: None} g_score: dict[str, int] = {start: 0} closed: set[str] = set() while frontier: g, _, current = heapq.heappop(frontier) if current in closed: continue if current == goal: # 경로 역추적 path = [] node: Optional[str] = goal while node is not None: path.append(node) node = came_from[node] return g, path[::-1] closed.add(current) for neighbor, cost in graph.get(current, []): if neighbor in closed: continue new_g = g + cost if new_g < g_score.get(neighbor, float("inf")): g_score[neighbor] = new_g came_from[neighbor] = current counter += 1 heapq.heappush(frontier, (new_g, counter, neighbor)) return None ``` A\* 구현과 구조가 거의 동일하다. 유일한 차이는 `heappush`에 넣는 키가 `g` 하나뿐이라는 점이다 — 휴리스틱 $h(n)$를 더하지 않는다. 사실상 [[A*]]에서 $h(n) = 0$으로 설정한 것과 같다. ## 시간 복잡도와 공간 복잡도 UCS의 시간 및 공간 복잡도는 $O(b^{1 + \lfloor C^* / \epsilon \rfloor})$이다. 여기서 $C^*$는 최적 해의 비용, $\epsilon$은 가장 작은 간선 비용이다. 이 표현은 "최적 비용 이하의 모든 노드를 확장해야 할 수 있다"는 의미로, 간선 비용이 아주 작으면($\epsilon \to 0$) 탐색 공간이 급격히 커진다. 모든 간선 비용이 동일하면 $C^* / \epsilon = d$(최적 해의 깊이)가 되어 BFS와 같은 $O(b^d)$이 된다. 이것이 "비용이 동일하면 UCS = BFS"라는 직관과 일치한다. ## Dijkstra 알고리즘과의 관계 Dijkstra 알고리즘과 UCS는 본질적으로 같은 알고리즘이다. 차이는 맥락에 있다. Dijkstra는 **단일 출발점에서 모든 노드까지**의 최단 거리를 구하는 문제에서 주로 언급되고, UCS는 **출발점에서 특정 목표까지**의 최단 경로를 찾는 탐색 문제에서 언급된다. UCS는 목표에 도달하면 즉시 종료하므로, 모든 노드를 처리하는 Dijkstra보다 일반적으로 더 일찍 끝난다. 또한 UCS는 [[Best-First Search]] 프레임워크의 인스턴스로 기술되므로, [[A*]]으로 자연스럽게 확장된다. $g(n)$에 휴리스틱 $h(n)$을 더하면 A\*가 되는 것이다. --- ## 출처 - Russell, S. and Norvig, P. (2021) *Artificial Intelligence: A Modern Approach*. 4th Global edn. Harlow: Pearson. Chapter 3.4.2, Figure 3.9. - Dijkstra, E. W. (1959) 'A note on two problems in connexion with graphs', *Numerische Mathematik*, 1(1), pp. 269–271. - Cormen, T. H. et al. (2022) *Introduction to Algorithms*. 4th edn. Cambridge, MA: MIT Press. Chapter 22.3 (Dijkstra's algorithm). [^aima-ucs]: Russell and Norvig (2021), Figure 3.9. AIMA 4판에서는 UCS를 BEST-FIRST-SEARCH에 PATH-COST를 평가 함수로 전달하는 한 줄짜리 함수로 정의한다. 이는 UCS가 Best-First Search의 특수한 경우임을 명확히 보여준다.