Polarux

처음으로 소개할 알고리즘은 미로를 생성하는 알고리즘이다.

딱히 엄청 복잡한 알고리즘은 아니지만 생성하는 방식에 대해서 고민해 본 것이다.

먼저 미로를 정의해보면,

1) 알고리즘을 일반화 하기 위해 직사각형 미로만을 고려한다.

2) 미로는 출발점과 도착점이 존재한다.

3) 미로의 모든 길은 순환하지 않는다.

- 말하자면, 잘못된 길로 들어가면 반드시 되돌아 나와야만 한다.

4) 미로는 사방이 막힌 칸이 존재하지 않는다.

1), 2) 는 크게 걱정할 부분이 아니므로 패스

3) 의 내용을 생각해보자. 미로의 모든 길은 순환하지 않는다. 여기서 뭔가 떠오르는 사람이 있다면, 자료구조 공부를 매우 열심히 한 사람일 것이다. 순환하지 않는 구조를 가지므로, 미로의 모든 길은 하나의 커다란 트리의 형태라고 할 수 있다.
백문이 불여일견. 예를 들어서 관찰해보자.

아래와 같은 미로가 있다고 가정하겠다.

이 트리는 위에서 정의한 4가지 조건을 모두 만족한다. 여기서 트리구조가 보인다면 이하 설명은 참고하지 않아도 좋다.

하지만 트리구조를 찾기 어려운 사람들을 위해 화살표와 점을 추가하면 아래와 같은 형태가 완성된다.

이렇게 보니 오히려 더 혼란스러울 수 있겠지만, 차근차근 설명해 보도록 하겠다.
일단 모든 원은 트리를 구성하는 노드이며, 화살표는 각 노드들의 서브 노드를 의미한다.
가장 큰 빨간색 원이 바로 루트이다. 그리고 주황색 원은 서브노드를 가지지 않는 리프 노드이다. 검은색 원은 서브노드를 1개 가지는 노드이며, 빨간색과 파란색은 각각 2개, 3개의 서브노드를 갖는 노드를 말한다.

결론적으로, 미로는 최대 3개의 서브노드를 가지는 하나의 트리구조가 되는것이다.

지금은 설명을 위해 (0, 0) 위치를 루트 노드로 잡았으나, 미로의 어떤 곳이라도 루트로 잡으면 항상 트리구조를 이루게 된다. 즉, 출발점을 어느곳으로 잡던 미로는 항상 트리구조를 만족한다는 의미가 될 수 있다.
(예외적으로 모든 방향이 개방된 곳을 루트로 잡을 경우, 루트는 4개의 서브노드를 가질 수 있다.)

알고리즘 : 1개의 부모노드와 3개의 서브노드를 가지며, 각각 겹치지 않는 위치(x, y)를 가지는 트리를 만든다면. 그 자체가 미로가 되는 것이다.

p.s. 자료구조 공부를 하고 싶은 사람들에게 꼭 추천하고 싶은 연습 예제이다.

ex) 아래의 그림들은 20x20 크기부터 면적비가 2배씩 커지는 미로이다.