미로 탐색 경주 — DFS vs BFS vs A*
같은 8×8 미로를 세 알고리즘이 풀어 탐사 칸 수(비용)와 경로 길이(품질)를 실측 비교한다 — DFS 23칸 경로, BFS·A* 15칸 최단, A*는 BFS보다 적은 탐사.
1 / 8같은 미로(8×8), 같은 출발·도착 — DFS·BFS·A*가 차례로 풉니다. 볼 것: 탐사한 칸 수(비용)와 찾은 경로 길이(품질).
DFSBFSA*
탐사 0칸 · 주황 = 출발/도착, 파랑 = 탐사, 초록 = 경로
단계 목록 · 키보드 ←/→ 이동, Space 재생
선택 기준은 두 축이다 — 최단이 필요한가(품질), 탐사를 아낄 수 있는가(비용). 아무 경로나 빨리면 DFS, 최단 보장이면 BFS, 최단 + 좋은 나침반이 있으면 A*.
왜 헷갈리는가
"DFS가 더 빨랐는데?"는 운이다 — DFS는 벽 방향이 맞으면 일찍 도착하지만 경로가 최단이라는 보장이 없고(이번 미로에서 23 vs 15), 방향이 어긋나면 온 미로를 헤맨다. 그리고 A*의 '빠름'은 휴리스틱의 품질이 좌우한다 — 나침반이 없거나 엉터리면 BFS와 같아지거나 오답을 낸다.
애니메이션이 보여주는 것
DFS는 한 방향으로 벽 끝까지 파고든다 — 탐사는 32칸으로 적었지만 경로는 23칸으로 멀리 돌았다. BFS는 물결이라 44칸을 적셨지만 경로 15칸은 '증명된 최단'이다. A*는 같은 최단을 35칸 탐사로 찾았다 — 맨해튼 거리라는 나침반이 목표 반대쪽 탐사를 잘라냈기 때문이다.
A*의 조건: 휴리스틱이 실제 남은 거리를 '과대평가하지 않으면'(admissible) 최단이 보장된다. 격자의 맨해튼 거리, 지도의 직선 거리가 그런 나침반이다.
실생활 선택 기준
무엇이 중요한지가 답을 고른다.
- 연결 여부만 알면 됨(이 방에서 저 방 갈 수 있나, 회로 도달성): DFS — 메모리도 경로 깊이만큼만.
- 이동 횟수 최소가 목적(퍼즐 최소 수, 무가중 네트워크 홉): BFS — 최단 보장이 필요한 순간 DFS는 오답.
- 지도·게임 길찾기(좌표가 있어 거리를 추정 가능): A* — 게임 업계의 사실상 표준. 내비는 여기에 계층화·양방향 탐색을 얹는다.
- 가중치가 있으면: BFS 대신 다익스트라, A*는 그 위에 나침반을 더한 것(다익스트라 = 휴리스틱 0의 A*).
- 메모리 주의: BFS/A*의 프런티어는 넓은 지도에서 폭발한다 — 깊이 제한 DFS·IDA* 같은 절충이 존재하는 이유.
기억할 것
- DFS = 아무 경로나 빨리(보장 없음), BFS = 최단 보장(넓은 탐사), A* = 최단 + 나침반 절약.
- A*의 보장 조건: 휴리스틱이 과대평가하지 않을 것(admissible).
- 다익스트라는 휴리스틱 0의 A* — 가중치가 생기면 BFS의 자리를 잇는다.
- 탐사 칸 수(비용)와 경로 길이(품질)를 분리해서 보는 것이 비교의 눈이다.