반응형
현재 위치에서 출구까지 가는 경로가 있으려면
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 = {
{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},
};
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 = { // 이동할 좌표
{-1, 0}, {1, 0}, {0, -1}, {0, 1},
};
public static void main(String[] args) {
print();
boolean result = findMazePath(0, 0);
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 |