Playground
경로 탐색
같은 지도에서 BFS, Dijkstra, A*의 탐색 과정과 최단 경로를 비교합니다.
지도를 편집하면 이전 탐색과 비교 결과가 지워집니다.
지도
21 × 15 · 상하좌우 이동
벽은 드래그, 시작·도착점은 눌러서 배치하세요. 방향키로 이동하고 편집 모드에서 Enter 또는 Space로 편집합니다.
- S시작
- G도착
- ▪벽
- ◦대기
- ·탐색
- ●경로
지도를 그리고 탐색을 시작해 보세요
탐색한 칸 0/경로 비용 —
| 알고리즘 | 탐색한 칸 | 이동 수 / 비용 | 결과 |
|---|---|---|---|
| BFS (선택됨) | — | — | 실행 전 |
| Dijkstra | — | — | 실행 전 |
| A* | — | — | 실행 전 |
알고리즘을 바꿔 실행하면 같은 지도의 결과가 표에 쌓입니다. 탐색한 칸은 시작·도착점을 포함한 확정 처리 수입니다. 이동 비용은 모두 1입니다.
알고리즘과 조작 방법
- BFS
- 가까운 칸부터 한 겹씩 넓혀 갑니다. 모든 이동 비용이 같을 때 최단 경로를 찾습니다.
- Dijkstra
- 누적 비용이 가장 작은 칸부터 탐색합니다. 이 지도는 모든 비용이 1이라 BFS와 탐색 양상이 같습니다.
- A*
- 누적 비용에 목표까지의 예상 거리를 더합니다. 상하좌우 거리인 맨해튼 거리로 목표 방향을 먼저 살펴봅니다.
벽과 지우개는 드래그하고, 시작·도착점은 눌러서 배치하세요. 시작·도착점 위에는 벽을 그릴 수 없습니다.
방향키로 칸을 이동하고 Enter 또는 Space로 편집합니다. 좁은 화면에서는 ‘이동’을 선택해 지도를 좌우로 밀어보세요. ‘편집’으로 돌아오면 다시 그릴 수 있습니다.
다른 탭으로 이동하면 일시정지합니다. 모션 감소 설정에서는 애니메이션 없이 결과를 표시합니다.
같은 지도에서 알고리즘을 바꿔 실행하면 결과가 비교표에 쌓입니다. 모든 이동 비용은 1이며, 탐색한 칸 수는 실행 시간 측정값이 아닙니다.