[알고리즘]랜덤 미로 생성 알고리즘: 엘러(Eller)의 알고리즘

  DFS나 BFS와 같은 여러 탐색 알고리즘들로 미로를 탐색할 수 있었죠?

 

 오늘은 미로를 직접 만들어보겠습니다. 

 

 미로를 만드는 알고리즘에는 여러가지가 있는데 그 중 Eller's Algorithm 엘러의 알고리즘을 살펴보겠습니다. 

 

 

• 랜덤 미로 생성 알고리즘 Eller's Algorithm

 엘러의 알고리즘은 미로를 한 행 씩 차례로 생성해나가는 방법입니다. 

 

 가장 빠르게 미로를 생성하는 알고리즘 중 하나이다.

 

 미로의 크기가 N이라면 시간복잡도는 O(N)으로, 미로를 선형시간 안에 만드는 엄청난 성능의 알고리즘입니다. 

 

 

• 생성 과정

3x5 크기의 미로를 생성하는 과정은 다음과 같습니다. 

 

 

1. 미로의 첫 번째 행을 초기화합니다. 

 

 이때 첫 번째 행에 속한 5개의 칸을 서로 다른 집합에 속하게 합니다. 

 

2. 현재 행에서 첫 번째 칸부터 마지막 칸까지 탐색하여 수평 경로를 만들어줍니다. 

 

인접해 있는 두 칸이 서로 다른 집합에 속해 있다면 두 칸 사이의 벽을 제거할지 남겨둘지 임의로 선택합니다.

이때 벽을 제거한다면 두 칸은 서로 같은 집합에 속하게 됩니다. 

 

 

3. 현재 행과 다음 행 사이의 수직 경로를 만들어줍니다. 

 

 이때, 같은 집합에 속한 칸들 중 적어도 하나는 수직 경로를 만들어야 합니다. 

 벽이 하나 제거가 되었다면, 같은 집합 속 나머지 칸에 대에 대해서 수직 경로를 만들지 말지는 임의로 선택합니다. 

 

 

4. 3.번에서 완성되지 않은 다음 행의 칸들의 집합을 정해줍니다. 

 

 

 

5. 마지막 행에 도달할 때까지 2.~4. 과정을 반복합니다. 

 

6. 마지막 행에 도달하면 인접해 있으면서 서로 다른 집합에 속한 칸들 사이의 모든 벽을 제거합니다.