미로 탐색 알고리즘

미로 탐색 알고리즘 (Maze Solving Algorithm) 중 가장 단순한 방법은 벽 따라가기 (Wall Follower) 방법이다. 벽 따라가기 방법은 미로의 오른쪽 또는 왼쪽 벽을 따라가는 미로 탐색 방법이다. 벽 따라가기 방법은 우선법 (Righ-hand rule) 또는 좌선법 (Left-hand rule)이 있다. 하지만, 다음과 같이 외벽과 내벽이 분리되어 있고 도착이나 출발 지점이 내부에 있으면 벽 따라가기 방법이 적용되지 않는다.

 

미로의 모든 경우에 사용할 수 있는 일반적인 미로 탐색 알고리즘은 깊이 우선 탐색 (DFS, Depth-first search)과 너비 우선 탐색 (BFS, Breadth-first search)이 있다. 보통 BFS가 더 짧은 경로를 찾는다.