미로찾기 알고리즘의 종류는 여러가지가 있다.
이 글은 그 중에서 가장 기본이 되는 재귀(recursive) 알고리즘에 관한 글이다.
재귀의 특징은 직관적으로 알아보기 쉽다는 이점이 있다.
재귀는 Stack을 사용하기 때문에 깊이가 깊어지면 overflow 에러가 날 가능성이 높아진다.
하지만, 간단한 문제에 대해서는 재귀의 유혹을 뿌리치기 힘들다.
이전에 알아봤던 깊이 우선 탐색은 미로찾기 알고리즘(재귀)의 원형이 된다.
2014/02/26 - [프로그래밍/알고리즘] - 하노이탑 재귀호출 알고리즘
2013/06/05 - [프로그래밍/알고리즘] - 탐색-깊이우선탐색, 너비우선탐색
오래전 포스팅한 내용이라...
예를 들어보면.
위와같은 길이 있다고 하자.
1.어두운 블럭은 벽으로 막혀 있다고 가정하고, 하얀 블럭은 갈 수 있는 길이다.
2. 입구에서 시작해서 출구까지 가는 길을 찾는 문제고, 다른 길은 없다.
3. 블럭 이외의 곳은 갈 수 없다.
위와 같이 직관적으로 알 수 있는 규칙을 세우고 2차원 배열로 위 길들을 표현할 수 있을 것이다.
|
1 2 3 4 5 6 7 8 9 10 11 |
int ar[8][10] = { 1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,1,1,1,1,1, 1,1,1,1,0,1,1,1,1,1, 1,1,1,1,0,1,1,1,1,1, 1,1,1,1,0,0,0,0,1,1, 1,1,1,1,1,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1 }; |
시작점은 배열의 요소 ar[1][0]다
끝점은 ar[7][7]다
생각해보자,
1. 위치의 요소가 주어지면 왼쪽,오른쪽,위쪽,아래쪽의 방향으로 이동이 가능한가 파악해야 한다.
2. 파악이 되었다면 이동 가능한 곳으로 이동해야 한다.
3. 이동을 했다면 다시 1번을 파악해야 한다.
큰 틀에서 1,2,3번의 반복이고. 이런 재귀를 통해 이 문제를 해결해 보면,
|
1 2 3 |
void find(int i, int j) { f[i][j]=1; if(j+1<10&&ar[i][j+1]!=1&&f[i][j+1]==0) find(i ,j+1); } //i행,j열이 주어지면 어느 한방의 이동 조건을 주어야 한다. 이 조건은 방향에 따라서 다르다. //이 코드는 오른편 이동에 대한 조건이다. //블럭을 나가면 안되므로 j+1<10이고 //벽으로는 이동을 못하므로 오른편 위치가 ar[i][j+1]!=1 블럭이면 안된다. //마지막으로 f[i][j+1]은 f[8][10]의 ar과 똑같은 배열을 두어 이동한 자취를 표시해 주어야 한다. //표시하지 않는다면 무한루프에 빠질 것이다. |
다음은 모든 4방향에 대해 재귀를 구현한 것이다.
|
1 2 3 4 5 6 7 |
void find(int i, int j) { f[i][j]=1; if(j+1<10&&ar[i][j+1]!=1&&f[i][j+1]==0) find(i ,j+1); if(j-1>=0&&ar[i][j-1]!=1&&f[i][j-1]==0) find(i, j-1); if(i+1<8&&ar[i+1][j]!=1&&f[i+1][j]==0) find(i+1, j); if(i-1>=0&&ar[i-1][j]!=1&&f[i-1][j]==0) find(i-1, j); } |
아래코드는 전체 코드와 결과다
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <stdio.h>
int ar[8][10] = { 1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,1,1,1,1,1, 1,1,1,1,0,1,1,1,1,1, 1,1,1,1,0,1,1,1,1,1, 1,1,1,1,0,0,0,0,1,1, 1,1,1,1,1,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1 }; int f[8][10];
void find(int i, int j) { f[i][j]=1; printf("%d, %d\n",i,j); if(j+1<10&&ar[i][j+1]!=1&&f[i][j+1]==0) find(i ,j+1); if(j-1>=0&&ar[i][j-1]!=1&&f[i][j-1]==0) find(i, j-1); if(i+1<8&&ar[i+1][j]!=1&&f[i+1][j]==0) find(i+1, j); if(i-1>=0&&ar[i-1][j]!=1&&f[i-1][j]==0) find(i-1, j); } int main() { find(1,0); } |
아주 간단한 코드다.
위에 제시된 길은 외길로 갈래 길은 없지만, 깊이우선탐색방법이므로 위 코드는 다음과 같은 길 또한 모두 제대로 탐색을 한다.
여기까지 이해했으면 다음과 같은 길에 대해 생각해보자.
입구에서 출구까지 갈 수 있는 길이 2가지 방법이다.
우선 위 코드를 위 길에 대해서 실행해 보자.(ar[8][10]을 위 길에 맞게 수정)
입구에서 출구까지 길은 찾지만, 그 이후의 탐색은 단순히 방문하지 않은 길을 가는 것 뿐이다.
위 코드에서 재귀호출 내부를 보면 탐색의 호출 순서가 오른쪽, 왼쪽, 위, 아래 순이다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <stdio.h>
int ar[8][10] = { 1,0,1,1,1,1,1,1,1,1, 0,0,0,0,0,1,1,1,1,1, 1,0,1,1,0,1,1,1,1,1, 1,0,1,1,0,1,1,1,1,1, 1,0,1,1,0,0,0,0,1,1, 1,0,0,0,0,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1 }; int f[8][10];
void find(int i, int j) { f[i][j]=1; printf("%d, %d\n",i,j); if(j+1<10&&ar[i][j+1]!=1&&f[i][j+1]==0) find(i ,j+1); //오른쪽 탐색 if(j-1>=0&&ar[i][j-1]!=1&&f[i][j-1]==0) find(i, j-1); //왼쪽 탐색 if(i+1<8&&ar[i+1][j]!=1&&f[i+1][j]==0) find(i+1, j); //위쪽 탐색 if(i-1>=0&&ar[i-1][j]!=1&&f[i-1][j]==0) find(i-1, j); //아래 탐색 } |
참고로 이 순서가 최초로 탐색하게 될 길을 결정한다.
위 코드는 단순하게 이 순서에 따라서 방문하지 않은 길을 방문하는 것 뿐이다.
여기서 출구를 찾는 프로그램으로 업그레이드를 할 필요가 있다.
첫 번째로, 방문한 곳이 출구인지 검사하는 코드가 필요하다.
두 번째로, 출구까지 가는 여러 길이 있는 경우 겹치는 길들이 있다. 그렇기 때문에 재귀의 회귀를 하는 경우 f[i][j]를 0으로 돌려 놓아야 한다.
그러면 재귀의 회귀는 언제 이루어지나.? 배열의 한 요소(길의 한 블럭)이 모든 방향을 다 검사한 후 재귀의 회귀가 이루어진다. 이는 하나의 함수가 파괴되는 과정이다. 또한 스택에서 하나의 함수가 빠져나가는 과정이고, 전체 과정에서 본다면 부분적 탐색의 과정이 끝남을 나타낸다. 물론 회귀의 후엔 새로운 깊이가 새로 생기고, 더 깊게 탐색을 들어갈 수 도 있다. 이 탐색은 여러 탐색의 깊이 중 하나의 깊이이고 이 과정이 회귀된다는 의미는 자신이 파괴되기 때문에 자신으로 인해 더 이상 파생되는 깊이가 생기지 않는 다는 의미다.
끝난 부분 탐색은 더 이상 f[][]를 참조할 필요가 없기 때문에 0으로 돌려 놓는다.
다시말해 f[][]=0으로 해 놓는 다는 의미는 각각의 탐색과정에서 f[][]를 사용 후 다른 탐색 과정(아직 그곳을 탐색하지 않은)을 위해 돌려 놓는다는 의미다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <stdio.h>
int ar[8][10] = { 1,0,1,1,1,1,1,1,1,1, 0,0,0,0,0,1,1,1,1,1, 1,0,1,1,0,1,1,1,1,1, 1,0,1,1,0,1,1,1,1,1, 1,0,1,1,0,0,0,0,1,1, 1,0,0,0,0,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1, 1,1,1,1,1,1,1,0,1,1 }; int f[8][10];
void find(int i, int j) { f[i][j]=1; printf("%d, %d\n",i,j); if(i==7&&j==7) printf("Find End\n");
if(j+1<10&&ar[i][j+1]!=1&&f[i][j+1]==0) find(i ,j+1); if(j-1>=0&&ar[i][j-1]!=1&&f[i][j-1]==0) find(i, j-1); if(i+1<8&&ar[i+1][j]!=1&&f[i+1][j]==0) find(i+1, j); if(i-1>=0&&ar[i-1][j]!=1&&f[i-1][j]==0) find(i-1, j); f[i][j]=0; }
int main() { find(1,0); } |
위 코드는 이동 가능한 모든 길을 탐색을 한다.
하지만 세련되지 못하다. 탐색 과정에 필요 없는 길(노란표시)들을 포함하여 출력하지만, 나름 쓸만하다.
길이 너무 길어져서. 마지막으로 입구->출구까지 갈 수 있는 모든 최단 거리만 출력하도록 하는 것은 다음 포스팅으로 미뤄야 겠습니다.