본문 바로가기

알고리즘/Algorithm

Recursion의 응용 - 미로찾기

반응형

현재 위치에서 출구까지 가는 경로가 있으려면

1. 현재 위치가 출구이거나

2. 이웃한 셀들 중 하나에서 현재의 위치를 지나지 않고 출구까지 가는 경로가 있거나

 

미로찾기(Decision problem)

1
2
3
4
5
6
7
8
9
10
public boolean findPath(x,y) {
       if(x, y) is the exit
            return true;
        else
            for each neighbouring cell(x', y') of (x, y) do
                if(x', y') is on the path way
                    if findPath(x', y');
                        return true;
                return false;
    }
cs

 

위 코드의 경우 (x, y)와 (x', y')가 서로 왔다갔다 하면서 무한루프에 빠질 수 있다.

1
2
3
4
5
6
7
8
9
10
11
public boolean findPath(x,y) {
       if(x, y) is the exit
            return true;
        else
            mark (x, y) as a visited cell;
            for each neighbouring cell(x', y') of (x, y) do
                if(x', y') is on the path way and not visited
                    if findPath(x', y');
                        return true;
                return false;
    }
cs

 

다른 방법은 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
public boolean findPath(x,y) {
        if(x, y) is either on the wall or a visited cell
            return false;
        else if (x, y) is the exit
            return true;
        else
            mark (x, y) as a visited cell;
            for each neighbouring cell(x', y') of (x, y) do
                if findPath(x', y');
                    return true;
                return false;
    }
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
57
58
59
60
61
public class Main {
    private static int N = 8// 미로 크기 NxN
    private static int [][] maze = {
            {00000001},
            {01101101},
            {00010001},
            {01001100},
            {01110011},
            {01000101},
            {00010001},
            {01110100},
    };
    private static final int PATHWAY_COLOR = 0// 길
    private static final int WALL_COLOR = 1;    // 벽 
    private static final int BLOCKED_COLOR = 2// 방문했지만 길이 아닌경우
    private static final int PATH_COLOR = 3;    // 방문했던 길
    
    static int[][] path = { // 이동할 좌표
        {-10}, {10}, {0-1}, {01},
    };
    
    public static void main(String[] args) {
        print();
        boolean result = findMazePath(00);
        System.out.println(result);
        print();
    }
    
    public static void print() { // 미로를 표시해 주는 함수
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }
    
    public static boolean findMazePath(int x, int y) {
        if(x < 0 || y < 0 || x >= N || y >= N) { // x, y 값이 미로를 벗어난 경우
            return false;
        }else if(maze[x][y] != PATHWAY_COLOR) { // 길이 아닌 경우
            return false;
        }else if(x == N-1 && y == N-1) { //출구인 경우
            maze[x][y] = PATH_COLOR;
            return true;
        }else {
            maze[x][y] = PATH_COLOR;
            for(int i = 0; i < 4; i ++) {
                int nx = 0;
                int ny = 0;
                nx = x + path[i][0];
                ny = y + path[i][1];
                if(findMazePath(nx, ny)) {
                    return true;
                }
            }
            maze[x][y] = BLOCKED_COLOR; // x, y 좌표에서 길이 없는 경우 표시
            return false;
        }
    }
}
cs

 

00000001
01101101
00010001
01001100
01110011
01000101
00010001
01110100
true
30000001
31101101
30010001
31001100
31112211
31333121
33313331
21112133

 

결과를 보면 길을 잘 찾은것을 볼 수있다.

반응형

'알고리즘 > Algorithm' 카테고리의 다른 글

Dynamic Programing 피보나치  (0) 2022.01.04
2진검색 알고리즘  (0) 2021.01.19
Recursion(순환)-3  (0) 2021.01.19
Recursion(순환)-2  (0) 2020.07.05
선형 시간 알고리즘  (0) 2020.07.05