미로 만들기

계산 방법

미로는 재귀 백트래킹, 곧 깊이 우선 탐색으로 팝니다. 벽이 모두 닫힌 상태에서 무작위 칸 하나를 출발점으로 삼고, 아직 가 보지 않은 옆 칸을 무작위로 골라 그 사이 벽을 허물며 나아갑니다. 더 갈 곳이 없는 칸에 닿으면 왔던 길을 되짚어 아직 안 가 본 이웃이 있는 칸을 찾습니다.

모든 칸을 한 번씩 들르고 한 걸음마다 벽을 하나만 열기 때문에 순환이 없는 완전 미로가 됩니다. 모든 칸이 이어져 있고 통로는 정확히 (칸 수 - 1)개이며, 어떤 두 칸 사이에도 길은 하나입니다. 이 방식은 갈림길이 적고 길게 구불구불한 통로가 잘 생깁니다.

정답은 입구에서 시작하는 너비 우선 탐색으로 찾아 가장 짧은 길을 냅니다. 완전 미로는 길이 하나뿐이니 그 길이 곧 정답입니다.

미로 번호는 유사 난수 생성기의 시드입니다. 시드와 크기가 같으면 늘 같은 미로가 나오므로 번호만 알려 줘도 미로를 공유할 수 있습니다.