미로찾기 알고리즘(recursive)-재귀

미로찾기 알고리즘의 종류는 여러가지가 있다. 

이 글은 그 중에서 가장 기본이 되는 재귀(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);

}



위 코드는 이동 가능한 모든 길을 탐색을 한다.

하지만 세련되지 못하다. 탐색 과정에 필요 없는 길(노란표시)들을 포함하여 출력하지만, 나름 쓸만하다.


길이 너무 길어져서. 마지막으로  입구->출구까지 갈 수 있는 모든 최단 거리만 출력하도록 하는 것은 다음 포스팅으로 미뤄야 겠습니다.


이 댓글을 비밀 댓글로
    • 자바송장
    • 2017.12.06 09:58
    안녕하세요 2차원배열 공간탐색을 찾다가와서 많이 배우고 갑니다.

    의문이 있어서 그러는데 오른탐색이라고 하셨는데 오른탐색은 미로를 걷는 사람의 우측으로만 진행하면

    언젠가는 도착지점에 도착한다라는 내용인것으로 알고 있습니다.

    현재 알고리즘은 우>좌>상>하 의 순서로 돌아가고 있는 것 같은데

    미로 진행방향 파라미터를 추가하여 우측만을 검색하는것이 맞지않나 생각해봅니다.

    2번째 예제의 순서로 살펴보면 (중간단계를 생략한) {1,0},{1,1},{1,5},{4,5},{4,4},{7,4},{7,7} 이런식으로요

    너무 오래전에 작성하신거라 뒷북처럼 보이네요. ㅎㅎ

    유용한 자료가 너무많네요 한번씩 다 읽어보겠습니다. ㅎㅎ
    • 호주웨노자
    • 2020.03.28 18:15
    f[8][10] 이 배열의 의미를 잘 모르겠어요 ㅠㅠ
    • 안녕하세요. f 배열은 일종의 메모리입니다. flag의 약자로 f라고 썼구요. ar배열과 동일한 크기의 공간이며 이동 경로의 자취를 기록하는 용도로 사용합니다. 예를들어 우리가 길을 기억하기 위해 나뭇가지를 땅에 놓아두어 지나온 길을 기억하는 것 처럼 말입니다. 여기에선 1이 나뭇가지가 놓인 길입니다. (0은 처음온길)