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

Posted by 돼지로운생활
2017. 12. 17. 23:36 개발자의 길/알고리즘

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



[미로 표현]


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

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

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


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

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


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

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 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}
 
        };
cs


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

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

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


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

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

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


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

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


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


[동 서 남 북 표현]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
cs




[전체코드]


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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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(10);
 
    }
 
    
 
 
 
    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 ;
    
 
    }
 
}
cs



유용한 IT정보 / 전자제품 리뷰
포털에서 MilkyeWay를 검색해주세요👍
유용한 정보였다면 ❤️ 클릭 부탁드려요 😄

이 댓글을 비밀 댓글로