알고리즘 튜토리얼

A* Quest

매일 쓰는 길찾기 — 어떻게 가장 빠른 길을 찾을까?

학습 시작하기

§1 · 왜 A*인가?

매일 10억 명이 사용하는 수학

스마트폰으로 길을 검색할 때, 게임 속 NPC가 장애물을 피해 달려올 때 — 그 뒤에는 같은 알고리즘 가족이 있습니다.

이 튜토리얼은 왜?라는 질문에서 출발합니다.

Google Maps

"10억 명의 길찾기"

Google Maps는 매월 10억 명 이상이 사용합니다. 교차로 수백만 개를 연결하는 그래프에서 최단 경로를 실시간으로 찾는 핵심에 A*계열 알고리즘이 있습니다.

출처: Wikipedia / Google Maps

게임 NPC · Tanktics (1982)

"U자 호수를 돌아라"

Chris Crawford의 전쟁 게임 Tanktics에서 탱크 NPC는 U자 모양 호수를 만났을 때 길을 찾아야 했습니다. 이 문제를 풀기 위해 A*가 게임에 처음 도입되었습니다.

출처: Pathfinding Wiki

§2 · 그래프란?

A*는 그래프만 봅니다

"A* doesn't see anything else. It only sees the graph."
— Red Blob Games

교차로를 노드(점), 도로를 엣지(선)로 추상화하면 현실의 지도가 그래프가 됩니다. A*는 이 그래프 위에서 시작 노드부터 목표 노드까지의 최적 경로를 탐색합니다.

§3 · 순진한 탐색

BFS: 모든 방향으로 균일하게

BFS(너비 우선 탐색)는 시작 셀에서 파문처럼 사방으로 퍼집니다.

비용을 고려하지 않기 때문에 모든 방향을 똑같이 탐색합니다. 목표가 어디 있든 상관없이 퍼지는 것이 특징입니다.

§4 · 비용의 도입

Dijkstra: 비용을 반영하면

도로마다 통행 비용이 다릅니다. Dijkstra는 누적 비용 g(n)을 기준으로 탐색해 진짜 최단 경로를 찾습니다.

하지만 목표 방향을 모르기 때문에 여전히 사방을 고르게 탐색합니다.

§5 · 휴리스틱

Greedy: 목표만 바라보기

휴리스틱 h(n)은 현재 위치에서 목표까지의 추정 거리입니다.

Greedy는 h(n)만 보기 때문에 장애물이 없을 때는 빠르지만, 벽을 만나면 잘못된 경로로 빠질 수 있습니다. 빨라 보이지만, 최단이 아닐 수 있어요.

§6 · A*의 직관

Dijkstra의 정확성 + Greedy의 방향성

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

과거 비용 + 미래 추정 = 총 기대 비용

g(n)

출발점에서 현재까지
실제 비용

h(n)

현재에서 목표까지
추정 비용 (휴리스틱)

f(n)

총 기대 비용
(탐색 우선순위)

§7 · 놀이터

직접 실험해 보세요

셀을 클릭/드래그하여 벽을 그리세요. 시작(초록)과 목표(빨강)를 드래그하여 이동할 수 있습니다.

시작

목표

벽

열린 목록

닫힌 목록

경로

Manhattan

Euclidean

Chebyshev

§9 · 한계와 변형

실제 세계는 더 복잡합니다

교통 정체는 엣지 가중치를 실시간으로 바꿉니다. Waze 같은 앱은 A*를 재실행하거나 D* Lite 같은 동적 알고리즘을 사용합니다.

HPA*(계층적 A*)는 수백만 타일 지도를 클러스터로 나누어 탐색 공간을 줄입니다. 메모리 한계가 있다면 SMA*나 IDA*처럼 공간 효율적인 변형을 선택할 수 있습니다.

Waze

실시간 교통 정보로 엣지 가중치를 업데이트하고 A*를 재실행합니다.

HPA* (Hierarchical A*)

6백만 타일 지도를 100개 클러스터로 분할해 탐색 공간을 대폭 줄입니다.

SMA* / IDA*

메모리 제한 환경에서 공간 효율적으로 동작하는 A* 변형입니다.

01
f(n) = g(n) + h(n) — 과거 비용과 미래 추정의 합산.
02
허용 가능한(admissible) 휴리스틱이면 A*는 최적 경로를 보장합니다.
03
BFS → Dijkstra → Greedy → A* 순으로 발전했습니다.
04
Manhattan은 4방향, Euclidean은 실거리, Chebyshev는 8방향에 적합합니다.
05
실제 앱은 A*를 확장하거나 조합해 더 큰 문제를 풉니다.