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

크루스칼 알고리즘은 미로 생성에 적용할 수 있는 최소 신장 트리 알고리즘입니다. 특히 완벽한 미로를 만드는 데 효과적입니다. 크루스칼 알고리즘의 대안은 Prim 알고리즘인데, 이 역시 최소 신장 트리 알고리즘이지만, 둘 다 동일한 미로를 생성하고 크루스칼이 더 빨리 실행되기 때문에, 저는 Prim 알고리즘을 구현하는 데 신경 쓰지 않았습니다.

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

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

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

크루스칼의 알고리즘은 미국의 수학자, 통계학자, 컴퓨터 과학자인 조셉 버나드 크루스칼 주니어가 만들었습니다. 그는 1956년 논문 "그래프의 최단 스패닝 서브트리와 순회 세일즈맨 문제"에서 처음으로 이 알고리즘을 설명했습니다.

이 알고리즘은 그래프의 최소 신장 트리(MST)를 찾고 모든 정점이 사이클을 피하면서 가능한 최소한의 총 에지 가중치로 연결되도록 설계되었습니다.

미로 생성을 위한 Kruskal 알고리즘의 작동 방식

1단계: 초기화

• 미로의 각 셀을 별도의 세트(고유한 구성 요소)로 취급합니다.
• 인접한 셀 사이의 모든 벽을 잠재적인 모서리로 나열합니다.

2단계: 벽 정리

• 벽을 섞거나 무작위로 정렬합니다. 진정한 크루스칼 알고리즘으로 구현하는 경우, 벽을 무작위 순서로 정렬합니다(미로 생성에는 가중치가 필요하지 않으므로).

3단계: 벽 처리

• 섞인 벽을 반복해서 통과합니다.
• 벽으로 나뉜 두 개의 셀이 다른 집합에 속하는 경우(즉, 미로에서 아직 연결되지 않은 경우), 벽을 제거하고 집합을 병합합니다.
• 이미 같은 세트에 속해 있다면 순환을 피하기 위해 벽을 건너뜁니다.

4단계: 완료될 때까지 계속

• 모든 셀이 연결되고 단일 스패닝 트리가 형성될 때까지 이 과정을 반복합니다.
• 결국 각 세포는 루프나 고립된 구간 없이 다른 세포와 연결됩니다.

크루스칼 알고리즘은 집합 병합에 의존하기 때문에, 미로 생성 중에 연결된 셀을 추적하는 효율적인 방법을 제공하는 Union-Find 알고리즘을 사용하여 최적화할 수 있습니다. Union-Find 알고리즘의 PHP 구현은 여기에서 볼 수 있습니다: PHP에서의 분리된 집합(Union-Find 알고리즘)