미로의 자료구조

학기 중에 미로를 저장하고 최단 경로를 탐색하는 과제가 있었다. 당시에는 스택까지만 배운 상태여서 배열에 미로를 저장하였다. 하지만 이번에 미로를 생성하는 알고리즘을 구현하면서 더 이용하기 편한 형태로 미로를 저장할 기회가 있었다. 바로 그래프의 형태로 구현하는 것이다. 이에 대하여 설명하고자 한다. 지나갈 수 있는 칸과 그렇지 않은 칸들로 이루어진 형태의 미로는 다루지 않겠다.

배열로 저장하기

인간이 바라보는 미로 자체에는 크게 복잡한 정보가 존재하지는 않는다. 단 두가지, 지나갈 수 있는 통로와 지나갈 수 없는 벽이 존재할 뿐이다. 칸을 모두 저장하면서 각 칸의 네 벽에 대한 정보를 저장하는 것은 분명 낭비가 있어보인다. 인접한 두 칸에서 저장한 정보가 겹치기 때문이다. 같은 값을 두 칸이 모두 저장할 필요가 있을까?

구현

가로 x개, 세로 y개의 칸을 갖는 미로는 다음과 같은 개수의 벽을 갖는다.

$$ x 개의 가로 벽 * (y +1) + (x+1 개의 세로 벽) * y $$

따라서 가로 벽과 세로 벽을 각각 배열로서 저장할 수 있다. 가로 벽 배열을 H, 세로 벽 배열을 V이라고 할 때, 칸 (x, y)을 둘러싼 벽은 다음과 같이 구할 수 있다(0 <= x, 0 <= y이며 모두 0부터 시작한다면).

위쪽 벽: H[y][x]

아래쪽 벽: H[y+1][x]

왼쪽 벽: V[y][x+1]

오른쪽 벽: V[y][x+1]

정확한 인덱스는 다를 수 있지만 중요한 것은 함수 하나를 구현하면 단지 벽만을 저장했음에도 칸의 좌표를 통해 벽에 접근할 수 있다는 것이다. 탐색 알고리즘은 단지 좌표로 미로를 탐색할 수 있다.

그래프로 저장하기

한 편으로 미로는 그 자체로 그래프라고 생각할 수 있다. 칸은 정점이며 통로는 옆 정점으로 갈 수 있는 간선다. 따라서 벽은 무한한 가중치를 갖는 간선이다. 모서리를 제외한 모든 칸은 4개의 인접한 정점을 가질 수 있다. 인접한 두 정점에 서로로 갈 수 있는 간선을 저장하는 것은 양방향 간선을 뜻한다. 이는 특별한 규칙이 없는 이상 양방향으로 이동할 수 있다는 통로의 정의에 부합한다. 간선의 방향에 따라 다른 가중치를 부여하거나 일방향 간선으로 만드는 것은 특정 방향이 더 가기 쉽게 만들거나 일방통행으로 만들 수 있다.

현실의 길찾기를 생각해보자. 길찾기는 미로 탐색의 변형이라고 할 수 있다. 길은 여러 개일 수 있지만 어떤 길은 여러 이유로 선호되지 않고, 어떤 길은 선호된다. 그래프의 가중치가 이 역할을 한다. 만약 미로 그래프에서 각 간선이 서로 다른 가중치를 갖는다면 최단경로 탐색 알고리즘은 여러 경로 중에 가장 비용이 적은 경로를 선택할 것이다. 비록 그 경로가 일반적인 미로에서의 경로와는 다르겠지만 말이다.

통로에 아무런 가중치가 없는 미로에서 다익스트라 알고리즘은 나쁜 성능을 보인다. 그것은 마치 BFS 탐색과 다를 바 없을 것이다. 하지만 만약 통로에 가중치가 부여된다면 DFS, BFS를 뛰어넘는 성능의 여러 알고리즘을 사용할 수 있을 것이다.

구현

미로에 한정한다면, 모든 칸은 인접한 네 개의 칸을 갖는다(모서리 칸들은 그렇지 않다는 것에 주의하자). 따라서 방향에 따른 칸 포인터 배열로 이를 정의할 수 있다. 또한 방향에 따른 가중치 배열을 정의하여 가중치를 줄 수 있다. 칸 V(x, y)의 오른쪽 간선과 가중치는 다음과 같이 얻을 수 있다.

adjacentVertex[direction] , weight[direction] (0 <= direction < 4)

마치며

미로를 배열이 아닌 그래프로 저장하면 더 많은 공간을 필요로 한다. 배열로 저장할 때 (열림 혹은 닫힘 플래그 비트) * 2xy + x + y의 공간을 차지한다면, 그래프로 저장할 때는 (x좌표 정수 + y좌표 정수 + 4정점 포인터 + 4가중치 변수) * xy의 공간을 필요로 한다. 대강 가늠해도 더 많은 공간을 차지함을 알 수 있다.

하지만 사실 공간이 부족할 만큼 큰 미로를 생성할 일은 별로 없다. 더군다나 단방향 간선이나 방향에 따라 가중치를 다르게 줄 수 있는 그래프가 개인적으로는 더 매력적으로 다가온다.

미로의 칸을 배열로 구현한 코드는 여기에서, 그래프로 구현한 코드는 여기(헤더)(구현)에서 볼 수 있다.