미로(MAZE)찾기란 그림 1 처럼 출발지 (A)에서 도착지 (B)까지 가는 경로를 알고리즘적으로 푸는 방법이다.
길찾기 알고리즘이 필요한 대표적인 사례는 네이게이션이나 마이크로마우스이다.
[출처] https://www.hackster.io/jordanjameswong/micromouse-83dab7
마이크로마우스는 빠른시간 안에 미로의 정해진 구역에 도착해야 하는 문제를 풀기위해 길찾기 알고리즘이 성능이 매우 중요한데
미로를 탈출하려다가 막다른 길이 있을 때, 우측(오른쪽)으로 가는 우측법(right rule)과 좌측(왼쪽)으로 가는 좌측법(left rule) 또는 무작의(random)로 시도해보고 길을 찾아가는 방법도 있다.
하지만 우측법과 좌측법은 특정 미로에서 무한루프에 빠질수도 있는 단점이 있다.
이런 단점을 보안하고 성능을 더 빠르게하기 위해 다양한 알고리즘(플러드 필(flood-fill) 또는 시드 필(seed-fill) DFS/BFS, 다익스트라 알고리즘, A* 알고리즘 방식등)도 있는데 여기서는 북 -> 동 -> 남 -> 서 순으로 가는 방법을 선택해서 재귀적으로 길을 찾아 문제를 해결하는 방식을 사용해 보자.
그림2와 같은 8X8 미로가 있다고 하자 입구에서 출구까지 가는 경로를 찾는 문제이다.
미로를 프로그래밍적으로 표현 하기 위해 2차원배열을 선언할 것이고 갈수있는 길(pathway)은 0으로 가지 못하는 길인 벽(wall)은 아래처럼 1로 선언할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
|
private static int [][] maze = {
{0,0,0,0,0,0,0,1},
{0,1,1,0,1,1,0,1},
{0,0,0,1,0,0,0,1},
{0,1,0,0,1,1,0,0},
{0,1,1,1,0,0,1,1},
{0,1,0,0,0,1,0,1},
{0,0,0,1,0,0,0,1},
{0,1,1,1,0,1,0,0}
};
|
이제 문제를 재귀적으로 생각해야 하는데 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구(base case)이거나 or
2) 이웃한 셀들 중 하나에서 이미 가본 곳을 다시 지나지 않고(방문했던 셀을 다시 방문하지 않고), 벽을 회피하여 출구까지 가는 경로가 있어야 한다.
이것을 의사코드로 나타내면 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
|
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;
>Colored by Color Scripter
|
|
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
62
63
|
public class MazeMain {
static final int PATHWAY_COLOUR = 0; // 갈수있는 길
static final int WALL_COLOR = 1; // 갈수없는 길 -> 벽임.
static final int BLOCKED_COLOR = 2; // 이미 방문해봤는데 출구까지의 경로상에 있지 않음이 밝 혀진 cell
static final int PATH_COLOR = 3; // 방문하여 아직 출구로 가는 경로가 될 가능성이 있는 cell
private static int N=8;
private static int [][] maze = {
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 1, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 1, 0, 0},
{0, 1, 1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 1, 1, 0, 1, 0, 0},
};
public static void main(String[] args) {
findMazePath(0,0);
printMaze();
}
public static boolean findMazePath(int x, int y) {
if (x < 0 || y < 0 || x >= N || y >= N)
return false;
else if (maze[x][y] != PATHWAY_COLOUR)
return false;
else if (x == N-1 && y == N-1) {
maze[x][y] = PATH_COLOR;
return true;
}
else {
maze[x][y] = PATH_COLOR;
if (findMazePath(x-1, y) ||
findMazePath(x, y + 1) ||
findMazePath(x+1, y) ||
findMazePath(x, y - 1)) {
return true;
}
maze[x][y] = BLOCKED_COLOR; // dead end
return false;
}
}
public static void printMaze() {
for(int y = 0 ; y < N ; y++) {
for(int x = 0; x < N ; x++) {
}
}
}
}
Colored by Color Scripter
|
레퍼런스
'알고리즘(Algorithm) > 재귀(recursion)' 카테고리의 다른 글
| (재귀)피보나치 수열(Fibonacci Sequence) (0) | 2019.06.25 |
|---|---|
| (재귀)N-Queen 문제 (0) | 2019.06.25 |
| (재귀)Blob(Labeling) 알고리즘 (0) | 2019.06.25 |
| 재귀함수(Recursive Function)란? (0) | 2019.06.25 |
