미로에 대하여 - 역사, 완전 미로, 생성 방식, 풀이 요령

고전적인 미궁에는 선택이 없는 구불구불한 길 하나만 있습니다. 미로에는 갈림길과 막다른 길이 있어 어느 쪽으로 갈지 정해야 합니다. 산울타리 미로는 16세기부터 유럽 정원에서 인기를 끌었고, 종이 미로 퍼즐은 그때부터 꾸준히 사랑받고 있습니다.

완전 미로에는 고리도 막힌 구역도 없으며, 어떤 두 칸 사이에도 길이 정확히 하나입니다. 수학적으로 통로가 격자의 신장 트리를 이루므로, n칸짜리 미로에는 칸 사이의 통로가 정확히 n - 1개 있습니다.

재귀적 백트래커는 격자를 무작위로 돌아다니며 아직 방문하지 않은 칸으로 벽을 허물고, 막히면 되돌아갑니다. 갈래가 적은 긴 통로가 만들어집니다. 반면 프림 알고리즘은 한 칸에서 바깥으로 미로를 키우며 매번 무작위 이웃 칸을 연결하므로 짧은 막다른 길이 많이 생깁니다.

완전 미로에서는 한 손을 벽에 대고 따라가면 반드시 출구에 도착합니다. 가장 짧은 길은 아니지만 항상 통합니다. 출구에서 시작점 쪽으로 거꾸로 살펴보는 것도 도움이 되고, 발자취가 있으면 같은 막다른 길에 두 번 들어가지 않습니다.

자주 묻는 질문

미로와 미궁의 차이는 무엇인가요?

미궁은 선택이 없는 길 하나이고, 미로는 갈림길과 막다른 길이 있습니다. 일상에서는 두 말을 같은 뜻으로 쓰는 경우가 많습니다.

벽 따라가기 규칙은 항상 통하나요?

완전 미로에서는 그렇습니다. 모든 벽이 이어져 있기 때문입니다. 고리가 있는 미로에서는 섬 주위를 끝없이 돌 수 있습니다.

미로는 얼마나 커질 수 있나요?

여기서는 최대 100 x 100칸, 즉 시작점과 출구 사이에 길이 하나뿐인 10,000칸입니다.

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.