미로찾기
recursion 으로 해결하는 것이 가장 간편
현재 위치에서 출구까지 가는 경로가 있으려면,
- 현재 위치가 출구이거나, 혹은
- 이웃한 셀들 중 하나에서 다시 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
여기에서는 큰 문제를 쪼개서 해결하는 분할정복 기법을 통해 문제를 해결한다. 재귀로 해결할 수 있으며, 재귀에서는 다음과 같은 것을 고려해야 한다.
- 무한루프에 빠지지 않도록 항상 주의
- base case 가 반드시 있어야 한다
- 모든 recursion은 base case로 수렴해야 한다.
답이 yes or no 라면 (Decision problem)?
psuedo code
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 pathway
if (findPath(x', y'))
return true;
return false;
}
- 위의 코드는 어떤가?
- x’, y’에서 recursion을 돌릴 때, x,y가 다시 인접한 셀이 될 수 있기 때문에 무한히 두 셀을 왔다 갔다 할 수 있음.
- 어떻게 방지할 수 있을까?
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 pathway(not block) *and not visited
if findPath(x', y')
return true
return false;
조건문을 처음에 분기
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
실제 코드
public class Maze {
private static int N=8;
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,0,0,1,0,0,0,1}
{0,1,1,1,0,1,0,0}
} // 통로는 0, 벽은 1
private static final int PATHWAY_COLOUR = 0; // 갈 수 있는 길
private static final int WALL_COLOUR = 1; // 벽
private static final int BLOCKED_COLOUR = 2; // 이미 방문했지만 막힌 색
private static final int PATH_COLOUR = 3; // 이미 방문했지만 아직까지는 확실히 판정이 안된 경우
// 처음 녹색으로 칠하고, 출구가 없으면 붉은색으로 칠함.
public static void main(String[] args) {
printMaze();
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) // visited(green or red), or wall
return false;
else if (x==N-1 && y== N-1) // this point is exit
maze[x][y] = PATH_COLOUR;
return true;
else
maze[x][y] = PATH_COLOUR;
if (findMazePath(x-1, y) || findMazePath(x, y+1) || findMazePath(x+1, y) || findMazePath(x, y-1))
return true;
maze[x][y] = BLOCKED_COLOUR; // dead end, 즉 이 위치에서는 더이상 갈 수 없다.
return false;
}
}
출처: 권오흠 교수님 알고리즘 강좌