안드로이드 코틀린 미로 생성 알고리즘 (Randomized Prim's algorithm)

미로를 만드는 알고리즘은 정말 많습니다.

하지만 그 중에선 미로같이 생기지 않은 미로를 만드는 알고리즘도 정말 많습니다.

이런 모양은 분명 미로긴한데 미로라고 하기엔 너무 이상하게 생겼습니다.

 

위키백과(https://en.wikipedia.org/wiki/Maze_generation_algorithm)에 갖가지 방법이 소개되어있지만 하나같이 설명이 개떡같이 되어있으며 심지어는 그 개떡같은 설명을 찰떡같이 알아듣고 꾸역꾸역 구현해도 이상한 결과가 나오기도 합니다.

 

위키백과에 설명되어있는 Randomized Prim's algorithm(랜덤 프림 알고리즘)을 따라해서 구현한 한 사람은 자신이 구현한 미로가 이따구로 나온다면서 스택오버플로우에 질문 글(https://stackoverflow.com/questions/29739751/implementing-a-randomly-generated-maze-using-prims-algorithm)을 올려놓기도 했더라구요.

그러자 답변에 위키백과의 해당 설명은 진심으로 고쳐야만 하는 수준이라며 자신이 제대로 설명해주겠다며 다음과 같은 설명을 하였습니다. (참고로 이 질문과 답변이 7년 전에 달렸는데 2022년 현재도 아직 위키 백과의 설명은 바뀐 거 없이 여전히 개떡 같습니다.)

 

참고로 원문 그대로 설명하기엔 역시 좀 무리가 있어서 약간 제가 바꾸었습니다.

1. 처음 미로의 상태는 모든 칸이 벽이고 빈칸은 단 하나도 없는 상태입니다.
2. (1,1) 좌표의 벽을 빈칸으로 바꿉니다. 그리고 그 빈칸과 인접한 벽들을 wall list에 추가합니다. (테두리 제외)
3. wall list가 빌 때까지 다음 행동을 반복합니다.
   • wall list에서 랜덤하게 벽 하나를 선택하고, wall list 목록에서 해당 벽은 이제 제거합니다.
   • 만약 '선택한 벽'의 '진행 방향에 있는 칸'이 빈칸이 아닌 경우 iii. 을 진행합니다.
   • '진행 방향에 있는 칸'과 인접한 벽들을 wall list에 추가합니다. (테두리 제외)
   • '진행 방향에 있는 칸'과 아까 '선택한 벽'을 빈칸으로 바꿉니다.
4. wall list가 비었으면 미로가 완성되었다는 뜻입니다.

 

최대한 쉽게 설명했으나 글로만 보면 이해가 어려우므로 그림과 같이 다시 설명하겠습니다.

 

먼저 1번부터 다시 봅시다.

1. 처음 미로의 상태는 모든 칸이 벽이고 빈칸은 단 하나도 없는 상태입니다.

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

이런 상태에서 시작합니다.

 

 

2. (1,1) 좌표의 벽을 빈칸으로 바꿉니다. 그리고 그 빈칸과 인접한 벽들을 wall list에 추가합니다.
(테두리 제외)

(1,1)을 빈칸으로 바꾸고 테두리를 제외하고 인접한 벽들을 wall list에 추가하면 이렇게 됩니다. (wall list에 추가된 벽들은 ⏪⏩⏫⏬로 표현했습니다.)

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⏩⬛⬛⬛⬛⬛⬛⬛⬛

⬛⏬⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

 

그리고 나서 wall list가 빌 때까지 다음을 반복합니다.

 

3 - i. wall list에서 랜덤하게 벽 하나를 선택하고, wall list 목록에서 해당 벽은 이제 제거합니다.

 

랜덤하게 wall list 벽 중에 (1,2) 좌표의 벽을 선택했다고 칩니다.

선택된 벽은 🟥으로 표현하였습니다.

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜🟥⬛⬛⬛⬛⬛⬛⬛⬛

⬛⏬⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

이제 🟥은 wall list에서는 제외되어 wall list에는 1개의 ⏬만 남아있게 됩니다.

 

3 - ii. 만약 '선택한 벽'의 '진행 방향에 있는 칸'이 빈칸이 아닌 경우 iii. 을 진행합니다.

여기서 '진행 방향에 있는 칸'이라는 것은 🟥가 원래 ⏩ 였으니 오른쪽 칸(1,3)을 말합니다.

진행 방향에 있는 칸을 🟪으로 표시하겠습니다.

🟪는 벽이었기 때문에 계속해서 iii으로 단계를 진행합니다.

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜🟥🟪⬛⬛⬛⬛⬛⬛⬛

⬛⏬⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

 

3 - iii. '진행 방향에 있는 칸'과 인접한 벽들을 wall list에 추가합니다. (테두리 제외)

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜🟥🟪⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

3 - iv. '진행 방향에 있는 칸'과 아까 '선택한 벽'을 빈칸으로 바꿉니다.

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

아직 wall list에 3개나 남아있으므로 다시 3 - i부터 반복합니다.

 

3 - i. wall list에서 랜덤하게 벽 하나를 선택하고, wall list 목록에서 해당 벽은 이제 제거합니다.

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛🟥⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

3 - ii. 만약 '선택한 벽'의 '진행 방향에 있는 칸'이 빈칸이 아닌 경우 iii. 을 진행합니다.

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛🟥⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛🟪⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

 

3 - iii. '진행 방향에 있는 칸'과 인접한 벽들을 wall list에 추가합니다. (테두리 제외)

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛🟥⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛🟪⏩⬛⬛⬛⬛⬛⬛⬛⬛

⬛⏬⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

3 - iv. '진행 방향에 있는 칸'과 아까 '선택한 벽'을 빈칸으로 바꿉니다.

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⬜⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬜⏩⬛⬛⬛⬛⬛⬛⬛⬛

⬛⏬⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

 

이걸 반복해서 쭉쭉 진행하면...

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⬜⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬜🟥🟪⬛⬛⬛⬛⬛⬛⬛

⬛⏬⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⬜⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬜🟥🟪⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⬜⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜🟥🟪⬛⬛⬛⬛⬛

⬛⬜⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜🟥🟪⏩⬛⬛⬛⬛

⬛⬜⬛⏬⬛⏬⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⏩⬛⬛⬛⬛

⬛⬜⬛⏬⬛⏬⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⏩⬛⬛⬛⬛

⬛⬜⬛🟥⬛⏬⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⏩⬛⬛⬛⬛

⬛⬜⬛⬛⬛⏬⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⏩⬛⬛⬛⬛

⬛⬜⬛⬛⬛⏬⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛🟥⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛🟪⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⏩⬛⬛⬛⬛

⬛⬜⬛⬛⬛⏬⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛🟥⬛⬛⬛⬛⬛⬛⬛

⬛⬛⏪🟪⏩⬛⬛⬛⬛⬛⬛

⬛⬛⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⏩⬛⬛⬛⬛

⬛⬜⬛⬛⬛⏬⬛⬛⬛⬛⬛

⬛⬜⬜⬜⏩⬛⬛⬛⬛⬛⬛

⬛⏬⬛⬜⬛⬛⬛⬛⬛⬛⬛

⬛⬛⏪⬜⏩⬛⬛⬛⬛⬛⬛

⬛⬛⬛⏬⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

... 쭉 진행하면

 

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛

⬛⬜⬛⬛⬛⬜⬛⬜⬛⬛⬛

⬛⬜⬜⬜⬛⬜⬜⬜⬜⬜⬛

⬛⬛⬛⬜⬛⬜⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬛⬜⬛⬜⬜⬜⬛

⬛⬛⬛⬜⬛⬛⬛⬜⬛⬛⬛

⬛⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛

⬛⬜⬛⬜⬛⬜⬛⬜⬛⬜⬛

⬛⬜⬛⬜⬛⬜⬜⬜⬛⬜⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

 

대충 이런 식으로 미로가 완성됩니다.

여기서 시작점(0,1)과 끝점(10, 9)를 빈칸으로 만들어주면

⬛⬜⬛⬛⬛⬛⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛

⬛⬜⬛⬛⬛⬜⬛⬜⬛⬛⬛

⬛⬜⬜⬜⬛⬜⬜⬜⬜⬜⬛

⬛⬛⬛⬜⬛⬜⬛⬛⬛⬛⬛

⬛⬜⬜⬜⬛⬜⬛⬜⬜⬜⬛

⬛⬛⬛⬜⬛⬛⬛⬜⬛⬛⬛

⬛⬜⬜⬜⬜⬜⬛⬜⬜⬜⬛

⬛⬜⬛⬜⬛⬜⬛⬜⬛⬜⬛

⬛⬜⬛⬜⬛⬜⬜⬜⬛⬜⬛

⬛⬛⬛⬛⬛⬛⬛⬛⬛⬜⬛

이렇게 미로가 완성됩니다.

 

이걸 이제 코틀린으로 구현해야하는데

아까 그 스택 오버플로우의 베스트 답변 글은 F# 언어로 구현되어있는 코드를 올려놔서

F#을 처음 보는 제 입장에서는 도저히 이해 안 되서 그 아래에 있던 두 번째 답변을 참고했습니다.

 

두 번째 답변은 자바 언어로 써놨더라구요. 그걸 보면서 저는 코틀린으로 바꾸었습니다.

 

package com.example.maze

import androidx.appcompat.app.AppCompatActivity
import android.os.Bundle
import android.util.Pair
import android.widget.TextView
import java.util.*

const val N = 51 // 미로 한 변의 길이

class MainActivity : AppCompatActivity() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        val tv = findViewById<TextView>(R.id.myTextView)

        val maze = Array<IntArray>(N) { IntArray(N) { 1 } } // 모든 칸이 1로 초기화 되어있는 미로를 생성한다.

        makeMaze(maze) // 미로를 생성한다.

        // 입구와 출구를 뚫는다.
        maze[0][1] = 0
        maze[N - 1][N - 2] = 0

        printMaze(maze, tv) // 출력한다.
    }

    private fun makeMaze(maze: Array<IntArray>) {
        val wallList = LinkedList<Pair<Cell, Cell>>()
        val start = Cell(1, 1)
        wallList.add(Pair(start, start)) // wall List에 (1,1)을 추가

        while (!wallList.isEmpty()) {
            // wallList에서 벽 하나를 랜덤하게 뽑아서 wallList에서 제거
            val wall = wallList.get(Random().nextInt(wallList.size))
            wallList.remove(wall)

            // 진행 방향에 있는 벽 좌표
            val r = wall.second.r
            val c = wall.second.c

            // wall의 진행 방향을 알아야 하기 때문에 wall 뿐만 아니라 wall 이전 벽에 대한 정보도 필요
            val previousR = wall.first.r
            val previousC = wall.first.c

            // 이전 벽에 대한 정보와 진행 방향에 있는 벽의 좌표를 이용해 그 사이에 끼여있는 벽의 좌표를 알 수 있다.
            val betweenR = (r + previousR) / 2
            val betweenC = (c + previousC) / 2

            if (maze[r][c] == 1) { // 진행 방향의 벽이 빈칸이 아니라면 주변벽을 wallList에 추가하고 between벽과 진행 방향에 있는 벽을 모두 빈칸으로 변경
                if (r >= 2 && maze[r - 2][c] == 1) {
                    wallList.add(Pair( Cell(r, c), Cell(r - 2, c) ))
                }
                if (c >= 2 && maze[r][c - 2] == 1) {
                    wallList.add(Pair( Cell(r, c), Cell(r, c - 2) ))
                }
                if (r < N - 2 && maze[r + 2][c] == 1) {
                    wallList.add(Pair( Cell(r, c), Cell(r + 2, c) ))
                }
                if (c < N - 2 && maze[r][c + 2] == 1) {
                    wallList.add(Pair( Cell(r, c), Cell(r, c + 2) ))
                }
                
                maze[r][c] = 0
                maze[betweenR][betweenC] = 0
            }
        }
    }

    private fun printMaze(maze: Array<IntArray>, tv: TextView) {
        val sb = StringBuilder()
        for (r in maze) {
            for (c in r) {
                sb.append(if (c == 1) '■' else ' ')
            }
            sb.append('\n')
        }
        tv.text = sb.toString()
    }

    data class Cell(val r: Int, val c: Int)
}

 

참고로 activity_main.xml엔 그냥 텍스트뷰 하나 밖에 없습니다.

<?xml version="1.0" encoding="utf-8"?>
<androidx.constraintlayout.widget.ConstraintLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    tools:context=".MainActivity">

    <TextView
        android:id="@+id/myTextView"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="Hello World!"
        android:textSize="3sp"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintLeft_toLeftOf="parent"
        app:layout_constraintRight_toRightOf="parent"
        app:layout_constraintTop_toTopOf="parent" />

</androidx.constraintlayout.widget.ConstraintLayout>

 

참고로 위 코드를 실시간으로 미로 생성되는 모양이 보이게 해주면 이렇게 보입니다.

미로를 생성하는 프림 알고리즘에 대해 알아보았습니다.