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

재귀적 백트래커 알고리즘은 본질적으로 범용적인 깊이 우선 탐색 알고리즘입니다. 미로 생성에 사용될 때는 경로를 무작위로 선택하도록 약간 수정되지만, 실제 탐색 목적으로 사용될 때는 일반적으로 각 레벨을 순차적으로 탐색합니다. 이 알고리즘은 길고 구불구불한 복도와 매우 길고 꼬불꼬불한 해답을 가진 미로를 생성하는 경향이 있습니다.

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

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

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

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

작동 방식

이 알고리즘은 스택 기반 깊이 우선 탐색 방식을 사용합니다. 단계별 설명은 다음과 같습니다.

1. 시작 셀을 선택하고 방문한 셀로 표시하세요.
2. 방문하지 않은 셀이 있는 동안: 아직 방문하지 않은 이웃 셀을 확인합니다. 방문하지 않은 이웃 셀이 하나 이상 있는 경우: 방문하지 않은 이웃 셀 중 하나를 무작위로 선택합니다. 현재 셀과 선택된 이웃 셀 사이의 벽을 제거합니다. 선택된 이웃 셀로 이동하여 방문한 것으로 표시합니다. 현재 셀을 스택에 추가합니다. 방문하지 않은 이웃 셀이 없는 경우: 스택에서 마지막 셀을 제거하여 되돌아갑니다.
3. 스택이 비어 있을 때까지 이 과정을 계속하십시오.

이 알고리즘에 대한 흥미로운 사실은 미로 생성기와 미로 해결기 두 가지 역할을 모두 수행할 수 있다는 점입니다. 이미 생성된 미로에 이 알고리즘을 실행하고 미리 설정한 종료 지점에 도달했을 때 중지하면 스택에 미로의 해답이 저장됩니다.

사실 이 사이트에는 이 알고리즘의 두 가지 버전이 있습니다. 하나는 이 페이지에 미로를 생성하는 LIFO 큐 기반 버전이고, 다른 하나는 미로를 비롯한 다른 알고리즘으로 생성된 미로를 푸는 재귀 기반 버전입니다 (해답이 표시된 지도는 이런 방식으로 만들어집니다). 두 가지 버전을 만든 건 그냥 재미 삼아 해본 것일 뿐이고, 어느 쪽이든 두 경우 모두에 똑같이 작동했을 겁니다 ;-)

추가 자료

이 글이 마음에 드셨다면 다음 제안도 마음에 드실 겁니다.

• 윌슨 알고리즘 미로 생성기
• 성장하는 나무 알고리즘 미로 생성기
• 엘러의 알고리즘 미로 생성기