맹목적 탐색 (BFS & DFS) 시뮬레이터

맹목적 탐색(무정보 탐색)은 알고리즘이 목표까지 얼마나 남았는지 전혀 모르는 상태로 탐색하는 방법입니다. 화면에 보이는 도착점·목표 노드(Node)는 여러분이 보라고 표시해 둔 것일 뿐, BFS와 DFS는 그 위치를 모른 채 정해진 순서대로 노드를 하나씩 확장해 볼 뿐입니다.

이 격자는 옆 칸으로 옮기는 비용이 어디서나 같습니다. 그래서 BFS가 찾아낸 경로는 언제나 가장 짧은 경로(최단 경로)입니다. DFS는 목표에 닿는 경로를 하나 찾을 뿐이라 그 경로가 가장 짧다는 보장이 없습니다. 같은 지도에서 두 알고리즘을 번갈아 실행해 경로의 길이를 비교해 보세요.

맵 편집 도구

탐색 알고리즘 설정

탐색 속도

실행 제어

대기 중

2D 평면 공간

시작 도착 벽 발견 방문 경로

탐색 트리 구조

환경 설정

최대 깊이

최대 자식

BFS와 DFS는 목표가 어디 있는지 모른 채 정해진 순서로만 노드를 확장합니다. 노드를 클릭하면 목표 노드(Goal)를 바꿀 수 있습니다.

알고리즘 선택

탐색 속도

실행 제어

대기 중

아직 확장 안 한 노드

현재 탐색 노드

탐색 완료 노드

목표 노드

지도 설정

방향 그래프 화살표가 가리키는 쪽으로만 갈 수 있습니다. 간선 비용 길마다 드는 비용이 다릅니다. 꺼 두면 모두 1입니다. 사이클 빙 돌아 제자리로 오는 길이 있습니다. 끄면 트리가 됩니다.

간선 끊기 켜면 간선(Edge)을 눌러 길을 막을 수 있습니다.

설정을 바꾸면 같은 지도를 그 설정으로 다시 그립니다 — 무엇이 달라지는지 비교해 보세요. 다른 지도를 보려면 새 지도를 누릅니다. 노드를 클릭하면 목표가 바뀝니다.

알고리즘 선택

한 번 넣은 노드는 다시 넣지 않기 끄면 이미 지나온 노드도 다시 넣습니다. 되돌아갈 길이 하나라도 있으면 끝나지 않습니다. 탐색 속도

실행 제어

대기 중

시작점

목표 노드

아직 확장 안 한 노드

현재 탐색 노드

탐색 완료 노드

찾은 길

참고 — 비용이 다를 때는 어떻게 할까

너비 우선 탐색이 찾는 것은 거쳐 가는 칸이 가장 적은 길입니다. 칸마다 드는 비용이 모두 같다면 그 길이 곧 가장 싼 길이기도 합니다. 그런데 간선 비용을 켜면 둘이 달라집니다 — 두 칸짜리 큰길이 세 칸짜리 골목보다 비쌀 수 있기 때문입니다.

균일 비용 탐색(uniform-cost search)은 다음에 확장할 노드를 여기까지 오는 데 든 비용이 가장 적은 것으로 고릅니다. 목표가 어디에 있는지는 여전히 모르므로 이것도 맹목적 탐색입니다 — 아는 것은 오직 지나온 길에 든 비용뿐입니다.

균일 비용 탐색은 교과 과정에서 다루는 내용이 아닙니다. 여기서는 「칸 수만 세면 손해를 볼 수 있다」를 눈으로 확인하는 데까지만 씁니다. 이 방법을 다익스트라 알고리즘이라고도 부릅니다 — 정보 이용 탐색 시뮬레이터에는 그 이름으로 들어 있으니, 이름이 둘일 뿐 같은 방법이라는 것만 알아 두면 됩니다. 이름까지 외울 필요는 없습니다.