크루스칼 알고리즘 미로 생성기

크루스칼 알고리즘은 미로 생성에 적용할 수 있는 최소 신장 트리 알고리즘입니다. 특히 완벽한 미로를 생성하는 데 매우 효과적입니다. 크루스칼 알고리즘의 대안으로 프림 알고리즘이 있는데, 이 또한 최소 신장 트리 알고리즘이지만 두 알고리즘이 생성하는 미로가 동일하고 크루스칼 알고리즘이 더 빠르기 때문에 프림 알고리즘은 구현하지 않았습니다.

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

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

크루스칼 알고리즘에 대하여

크루스칼 알고리즘은 미국의 수학자, 통계학자, 컴퓨터 과학자인 조셉 버나드 크루스칼 2세가 개발했습니다. 그는 1956년 논문 "그래프의 최단 신장 부분 트리와 외판원 문제에 관하여"에서 이 알고리즘을 처음으로 설명했습니다.

이 알고리즘은 그래프의 최소 신장 트리(MST)를 찾도록 설계되었으며, 모든 정점이 최소한의 총 간선 가중치로 연결되고 사이클이 발생하지 않도록 보장합니다.

크루스칼 알고리즘을 이용한 미로 생성 방법

1단계: 초기화

• 미로의 각 칸을 별개의 구성 요소(고유한 요소)로 취급하십시오.
• 인접한 셀 사이의 모든 벽을 잠재적 모서리로 나열하십시오.

2단계: 벽 분류하기

• 벽들을 섞거나 무작위로 배열하세요. 크루스칼 알고리즘을 그대로 구현한다면, 미로 생성에는 가중치가 필요하지 않으므로 벽들을 무작위 순서로 정렬하세요.

3단계: 프로세스 벽

• 섞인 벽들을 차례로 순회합니다.
• 벽으로 나뉜 두 칸이 서로 다른 집합에 속해 있다면 (즉, 미로에서 아직 연결되지 않았다면), 벽을 제거하고 두 집합을 합치세요.
• 이미 같은 세트에 속해 있다면 (순환을 방지하기 위해) 벽을 건너뛰세요.

4단계: 완료될 때까지 계속 진행하세요

• 모든 셀이 연결되어 하나의 신장 트리가 형성될 때까지 이 과정을 반복합니다.
• 마지막으로, 모든 세포는 고리나 고립된 부분 없이 서로 연결됩니다.

크루스칼 알고리즘은 집합 병합에 의존하기 때문에, 미로 생성 과정에서 연결된 셀을 효율적으로 추적하는 Union-Find 알고리즘을 사용하여 최적화할 수 있습니다. Union-Find 알고리즘의 PHP 구현 코드는 여기에서 확인할 수 있습니다: 링크

추가 자료

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

• 헌트 앤 킬 미로 생성기
• 윌슨 알고리즘 미로 생성기
• 성장하는 나무 알고리즘 미로 생성기