에듀테크 프로젝트 대시보드
미로 생성 알고리즘
완벽한 미로(perfect maze)는 모든 칸이 연결되고 고리(cycle)가 하나도 없는 격자 그래프의 스패닝 트리다. 칸을 노드로, 허문 벽을 간선으로 보면 N칸짜리 미로에는 정확히 N−1개의 벽이 헐린다. 아래에서 벽을 허무는 과정을 한 걸음씩 지켜보자.
무작위 DFS — 한 칸에서 출발해 아직 안 간 이웃을 무작위로 골라 벽을 허물고 이동한다.
막다른 곳에 닿으면 스택을 pop 해 갈림길까지 되돌아온다(백트래킹). 스택이 비면 끝.
결과는 통로가 길고 구불구불하며 갈림길이 적은 미로다.
무작위 Prim — 방문한 영역의 경계 벽을 모두 후보 목록에 넣고, 그중 하나를 무작위로 뽑아 반대편이 미방문이면 허문다. 최소 스패닝 트리의 Prim을 간선 가중치 없이 돌리는 셈이라 짧은 갈래가 사방으로 뻗는 미로가 된다.
Kruskal — 모든 내부 벽을 무작위 순서로 훑으며, 양쪽 칸이 find 로 다른 집합일 때만
허물고 union 한다. 같은 집합이면 허무는 순간 고리가 생기므로 건너뛴다.
왜 트리인가? 벽을 허물 때 "이미 연결된 두 칸"을 다시 잇지 않으면 절대 고리가 안 생긴다. 연결은 유지하면서 고리를 0으로 만든 그래프가 곧 스패닝 트리이고, 트리에서는 임의의 두 칸 사이 경로가 정확히 하나다. 그래서 완벽한 미로의 정답 길은 유일하다.
푸는 법 — 미로는 그래프이므로 BFS로 시작점에서 물결처럼 퍼뜨리면 도착점까지의 최단 경로를 얻는다. 각 칸에 "어디서 왔는지"(parent)를 기록해 두었다가 도착점에서 거꾸로 따라가면 길이 복원된다.
칸 N = 폭 × 높이, 허문 벽 = N − 1, 전체 벽 후보에서 남는 벽이 미로의 벽이다.
# 무작위 DFS (재귀적 백트래킹) — 반복(스택) 버전 def carve(grid, start): stack = [start] visited = {start} while stack: cell = stack[-1] nbrs = [n for n in neighbors(cell) if n not in visited] if not nbrs: stack.pop() # 막다른 길 → 되돌아감 continue nxt = random.choice(nbrs) remove_wall(cell, nxt) # 벽 허물기 = 간선 추가 visited.add(nxt) stack.append(nxt) # |visited| == N, 허문 벽 == N - 1 → 스패닝 트리