🧩 미로 생성 실험실
알고리즘이
즉석에서 미로를 만들어요
완전히 벽으로 막힌 격자에서 시작해서, "무작위로 아직 안 가본 이웃 칸으로 이동하며 벽을 허물기"를 반복하면 자동으로 완벽한 미로가 만들어져요. 생성 과정을 지켜보고, 시작(초록)부터 도착(빨강)까지 최단 경로도 확인해보세요.
알고리즘 (깊이 우선 탐색): 현재 칸에서 아직 방문 안 한 이웃 칸을 무작위로 골라 벽을 허물고 이동해요. 갈 곳이 없으면 이전 칸으로 되돌아가요(백트래킹). 모든 칸을 방문하면 미로가 완성돼요 — 이렇게 만든 미로는 항상 모든 칸 사이에 경로가 딱 하나씩만 있어요.
💡 이렇게 "가지가 갈라지지만 순환로가 없는" 구조를 그래프 이론에서는 신장트리(spanning tree)라고 불러요 — 최소 신장 트리 실험실에서 봤던 것과 같은 개념이 미로 생성에도 쓰이는 거예요.