재귀적 백트래커 미로 생성기

재귀적 백트래커 알고리즘은 실제로 일반적인 목적의 깊이 우선 탐색입니다. 미로 생성에 사용될 때는 무작위로 경로를 선택하도록 약간 수정한 반면, 실제 탐색 목적으로 사용될 때는 일반적으로 각 레벨을 선형 순서로 탐색합니다. 길고 구불구불한 복도와 매우 길고 꼬불꼬불한 솔루션이 있는 미로를 생성하는 경향이 있습니다.

완벽한 미로는 미로의 어느 지점에서 다른 지점까지 정확히 하나의 경로가 있는 미로입니다. 즉, 빙글빙글 돌다가 막다른 골목에 부딪혀 돌아서서 되돌아가야 하는 경우가 종종 있습니다.

여기에서 생성된 미로 지도에는 시작과 끝 위치가 없는 기본 버전이 포함되어 있으므로 미로의 어느 지점에서든 다른 지점으로 가는 해답을 직접 결정할 수 있습니다. 영감을 얻고 싶다면 제안된 시작 및 종료 위치를 활성화하고 두 위치 사이의 해법도 확인할 수 있습니다.

재귀적 백트래커 알고리즘은 완벽한 미로(루프가 없고 두 지점 사이에 단일 경로가 있는 미로)를 생성하기 위한 깊이 우선 탐색 방법입니다. 간단하고 효율적이며 길고 구불구불한 복도가 있는 시각적으로 매력적인 미로를 생성합니다.

이름과 달리 반드시 재귀를 사용하여 구현할 필요는 없습니다. 종종 LIFO 큐(즉, 스택)를 사용하여 반복적 접근 방식으로 구현됩니다. 매우 큰 미로의 경우 재귀를 사용하면 프로그래밍 언어와 사용 가능한 메모리에 따라 호출 스택 오버플로가 발생할 가능성이 더 큽니다. LIFO 큐는 사용 가능한 메모리가 부족한 경우 디스크나 데이터베이스에 큐를 보관하더라도 대량의 데이터를 처리하는 데 더 쉽게 적용할 수 있습니다.

작동 원리

이 알고리즘은 스택 기반 깊이 우선 탐색 접근 방식을 사용하여 작동합니다. 단계별 분석은 다음과 같습니다.

1. 시작 셀을 선택하고 방문한 것으로 표시하세요.
2. 방문하지 않은 셀이 있는 경우:
   • 아직 방문하지 않은 이웃 셀을 살펴보세요.
   • 방문하지 않은 이웃이 하나라도 있는 경우:
     • 방문하지 않은 이웃 중 하나를 무작위로 선택합니다.
     • 현재 셀과 선택한 이웃 사이의 벽을 제거합니다.
     • 선택한 이웃으로 이동하여 방문한 것으로 표시하세요.
     • 현재 셀을 스택에 푸시합니다.
   • 방문하지 않은 이웃이 없는 경우:
     • 스택의 마지막 셀을 꺼내서 뒤로 돌아갑니다.
3. 스택이 빌 때까지 이 과정을 계속합니다.

이 알고리즘에 대한 흥미로운 사실은 미로 생성기와 미로 해결기로 모두 작동한다는 것입니다. 이미 생성된 미로에서 실행하고 결정된 종착점에 도달했을 때 멈추면 스택에 미로에 대한 솔루션이 포함됩니다.

저는 실제로 이 사이트에서 이 알고리즘의 두 가지 버전을 사용합니다. 이 페이지에서 미로를 생성하기 위한 LIFO 큐 기반 버전과 미로를 풀기 위한 재귀 기반 버전입니다. 또한 다른 알고리즘에서 생성된 미로도 있습니다(해결책이 있는 맵이 만들어지는 방식입니다). 두 가지 다른 버전을 사용하는 것은 제가 그것을 흥미롭게 여기는 괴짜이기 때문에 스포츠를 위한 것일 뿐입니다. 어느 것이든 둘 다 작동할 수 있었을 것입니다 ;-)