미로 생성 알고리즘의 세계 — 같은 미로인데 알고리즘에 따라 성격이 완전히 달라진다

프로시저럴 생성의 가장 기본, 미로

프로시저럴 생성(procedural generation)이라는 말, 게임 개발에서 정말 많이 들리죠. 이게 뭐냐면, 사람이 하나하나 수작업으로 만드는 게 아니라 알고리즘이 자동으로 콘텐츠를 만들어내는 걸 말해요. 로그라이크 게임의 랜덤 던전, 오픈월드의 지형, 심지어 퀘스트 생성까지 — 이 모든 것의 뿌리를 거슬러 올라가면 미로 생성 알고리즘이 있어요.

미로 생성은 단순해 보이지만, 그 안에 그래프 이론, 자료구조, 무작위성 제어 같은 CS 핵심 개념들이 다 녹아 있어요. 1997년에 정리된 한 페이지가 지금까지도 개발자들 사이에서 레퍼런스로 공유되는 이유가 바로 그거예요. 시간이 지나도 변하지 않는 기본기이기 때문이죠.

오늘은 대표적인 미로 생성 알고리즘들을 하나씩 살펴보면서, 각각이 어떤 "성격"의 미로를 만들어내는지 비교해볼게요.

재귀 백트래커 — DFS의 창작 버전

코딩 테스트 공부하면서 DFS(깊이 우선 탐색) 많이 보셨죠? 미로 생성에 그대로 적용할 수 있어요.

동작 방식은 이래요. 시작 셀에서 출발해서 아직 방문하지 않은 이웃 셀 중 하나를 랜덤으로 골라요. 그쪽으로 벽을 허물고 이동하고, 또 거기서 이웃을 골라서 이동하고... 이걸 더 이상 갈 곳이 없을 때까지 반복해요. 막히면? 스택에서 이전 위치를 꺼내서 되돌아가요(백트래킹). 그리고 다른 방향을 시도하죠.

이렇게 만든 미로의 특징은 길고 구불구불한 통로가 생긴다는 거예요. 한번 들어가면 한참을 걸어야 하는 느낌이에요. 막다른 길(dead end)이 비교적 적어서, 미로를 푸는 사람 입장에서는 "계속 뭔가 진전이 있는 것 같은" 느낌을 줘요. 구현도 스택 하나면 되니까 가장 먼저 시도해보기 좋은 알고리즘이에요.

프림 알고리즘 — MST를 미로에 적용하면

최소 신장 트리(MST)를 구하는 프림 알고리즘, 알고리즘 수업에서 배우셨을 거예요. 이걸 미로 생성에 쓸 수 있다는 게 재밌는 부분이에요.

이게 뭐냐면, 미로를 그래프로 보는 거예요. 각 셀이 노드이고, 셀 사이의 벽이 간선이에요. 프림 알고리즘을 돌리면 모든 셀을 연결하는 트리가 만들어지는데, 그게 곧 미로가 되는 거예요. 벽 목록을 유지하면서 무작위로 벽을 골라 제거하되, 이미 연결된 셀은 건너뛰는 방식이에요.

프림으로 만든 미로는 DFS 미로와 성격이 확 달라요. 분기가 많고 통로가 짧아요. 여러 갈래로 뻗어나가는 형태라서 미로를 푸는 사람 입장에서는 선택지가 많아 더 헷갈릴 수 있어요. DFS 미로가 "좁은 골목길"이라면, 프림 미로는 "여러 갈래의 교차로가 많은 시장"에 가까워요.

크루스칼 알고리즘 — Union-Find의 실전 활용

역시 MST 알고리즘인 크루스칼도 미로에 적용돼요. 동작 방식이 프림과는 좀 달라요. 모든 벽을 목록에 넣고 랜덤으로 섞은 뒤, 하나씩 꺼내면서 "이 벽을 허물면 아직 연결 안 된 두 셀이 연결되나?"를 확인해요. 연결 안 된 경우에만 벽을 제거하고, 이미 같은 구역이면 건너뛰고요.

여기서 Union-Find(서로소 집합) 자료구조가 딱 들어맞아요. 두 셀이 같은 집합에 속하는지 확인하고, 다른 집합이면 합치는 — 코딩 테스트에서 자주 보는 그 패턴이 여기서 실전 활용되는 거예요. 크루스칼 미로는 프림이나 DFS보다 균일한 느낌을 줘요. 특정 방향으로의 편향(bias)이 적어서 꽤 자연스럽고 무작위한 미로가 만들어져요.

바이너리 트리 — 충격적으로 간단한 알고리즘

이건 "이게 돼?"라는 반응이 먼저 나오는 알고리즘이에요. 각 셀에서 위쪽 벽과 왼쪽 벽 중 하나를 동전 던지기로 골라서 제거해요. 끝이에요. 정말 이게 전부예요.

코드로 치면 이중 for문 안에 랜덤 하나면 돼요. 그런데 진짜 미로가 만들어져요. 대신 대가가 있죠. 북서쪽 모서리로 갈수록 통로가 뻥뻥 뚫리는 강한 편향이 생겨요. 실용적인 미로로 쓰기는 어렵지만, 알고리즘의 단순함이 결과물의 품질과 어떤 관계가 있는지 직관적으로 보여주는 아주 좋은 교보재예요.

엘러 알고리즘 — 한 줄씩 생성하는 마법

엘러(Eller) 알고리즘은 좀 특별해요. 다른 알고리즘들은 미로 전체를 메모리에 올려야 하는데, 엘러는 한 줄씩(row by row) 생성해요. 현재 줄의 정보만으로 다음 줄을 만들 수 있거든요. 이게 뭘 의미하냐면, 이론적으로 무한히 큰 미로도 일정한 메모리로 생성 가능하다는 거예요.

게임에서 끝없이 스크롤되는 던전을 만들고 싶다면, 엘러 알고리즘이 딱이에요. 메모리 효율이 중요한 임베디드 환경이나 모바일 게임에서도 유용하고요.

업계에서는 어떻게 쓰이나

이런 미로 알고리즘들은 게임 업계에서 프로시저럴 콘텐츠 생성(PCG)의 기초 블록이에요. Hades 같은 로그라이크의 방 배치, Minecraft의 동굴 생성, Spelunky의 레벨 디자인 같은 게 다 이런 알고리즘의 변형이에요.

최근에는 Wave Function Collapse(WFC)라는 더 고급 기법도 많이 쓰이는데, 이것도 결국 제약 조건 아래에서 타일을 배치하는 거라 미로 생성과 뿌리가 같아요. AI 기반 레벨 생성도 마찬가지로 이런 기본 알고리즘들의 아이디어를 확장한 거예요. 기초를 알면 응용이 보이는 전형적인 케이스죠.

실무에서, 그리고 공부에서

코딩 테스트 준비하면서 DFS, BFS, Union-Find를 열심히 공부하잖아요. 미로 생성은 이 자료구조와 알고리즘이 실제로 "창작"에 어떻게 쓰이는지 체감할 수 있는 최고의 예시예요. 문제를 "푸는" 것에서 한 발 더 나아가, 뭔가를 "만드는" 데 알고리즘을 활용하는 경험은 개발자로서의 시야를 넓혀줘요.

인디 게임을 만들고 있거나 프로시저럴 생성에 관심이 있다면, 이 알고리즘들을 직접 구현해보세요. 각각 50줄 이내로 구현 가능하고, 시각화까지 붙이면 포트폴리오 프로젝트로도 손색없어요. Python의 pygame이나 웹이라면 Canvas API로 금방 그럴듯한 데모를 만들 수 있거든요.