[알고리즘] 미로찾기 알고리즘 - 재귀함수

미로찾기알고리즘 - 재귀함수

[미로 표현]

- 아래와 같은 미로가 있다.

- 녹색은 숲으로 막혀있고 오직 흰색 길을 통해서만 나갈 수 있다.

- 숲으로 들어가면 야생 동물들에게 잡하먹히기에 갈 수가 없다.

위와 같은 규칙이 있다고 할 때 미로는 아래 사진과 같이 생겼을 것이고 이를 2차원 배열로 바꿔서 풀어보면

[9][10]의 배열이기 때문에 다음과 같이 나타낼 수 있습니다.

- 1은 갈 수 없는 길, 0은 갈 수 있는 길

- 시작은 [1][0], 출구는 [8][4]

 int[][] arr = 
 
        {
 
                {1,1,1,1,1,1,1,1,1,1},
 
                {0,0,0,0,0,0,1,1,1,1},
 
                {1,1,1,1,1,0,0,0,0,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,0,0,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,1,1,1}
 
        };

그렇다면 미로를 어떻게 빠져나갈 수 있을까요? 

정상적인 길을 찾아야 하는데 조금만 갈 수 있는 방향은 1방향일 수도 2방향일 수도 3방향일 수도 있겠네요.

그래서 그걸 코드로 구현을 해보도록 하겠습니다. 

1. 동, 서, 남, 북의 방향으로 이동이 가능한지 확인한다.

2. 이동이 가능하다면 이동을 한다.

3. 이동 후 다시 1번의 과정을 실행한다.

- 전체적인 맵의 크기는 정해져 있고 그 크기를 벗어날 수 없기 때문에 코드는 아래와 같이 표현을 하게 된다.

- 길이 맞다면 계속해서 탐색을 해야 하기 때문에 결국은 재귀함수의 호출을 통해서 길을 찾아낼 수 있다.

아래 코드는 4방향에 대해서 재귀함수 코드를 구현한 것입니다.

[동 서 남 북 표현]

N=9;
 
M=10;
 
int[][] arr2 = new int[N][M]; 
 
    if (i+1 < N && arr[i+1][j] != 1 && arr2[i+1][j] == 0) find (i+1,j);    
 
    if (i-1 >= 0 && arr[i-1][j] != 1 && arr2[i-1][j] == 0) find (i-1,j);    
 
    if (j+1 < M && arr[i][j+1] != 1 && arr2[i][j+1] == 0) find (i,j+1);    
 
    if (j-1 >= 0 && arr[i][j-1] != 1 && arr2[i][j-1] == 0) find (i,j-1);

[전체코드]

public class miro{
 
    public static int N        = 10;
    public static int M        = 9;
    
 
 int[][] arr = 
 
        {
                {1,1,1,1,1,1,1,1,1,1},
                {0,0,0,0,0,0,1,1,1,1},
                {1,1,1,1,1,0,0,0,0,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,0,0,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,1,1,1}
        };    
 
 int[][] arr2 = new int[9][10];    
 
    public static void main(String args[]) {
 
        miro tt = new miro();
        tt.find(1, 0);
 
    }
 
    
 
 
 
    public void find(int i, int j) {    
 
        arr2 [i][j] = 1;
        System.out.println(i + ", " + j);
        
 
        if (i == 8 && j == 4) 
            System.out.println("EXIT");
    
        if (i+1 < N && arr[i+1][j] != 1 && arr2[i+1][j] == 0) find (i+1,j);
 
        if (i-1 >= 0 && arr[i-1][j] != 1 && arr2[i-1][j] == 0) find (i-1,j);    
 
        if (j+1 < M && arr[i][j+1] != 1 && arr2[i][j+1] == 0) find (i,j+1);    
 
        if (j-1 >= 0 && arr[i][j-1] != 1 && arr2[i][j-1] == 0) find (i,j-1);        
 
        arr2[i][j] = 0 ;
    
 
    }
 
}