인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.
미로찾기
현재 위치에서 출구까지 가는 경로가 있으려면
-
현재 위치가 출구이거나 혹은
-
이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
미로찾기(Decision Problem)
Decision Problem: 답이 yes or no인 문제
boolean findPath(x,y)
//Base case
if(x,y) is the exit
return true;
//Recursice case
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;
가본 위치와 가지 않은 위치를 구분
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 and not visited
if findPath(x',y')
return true;
return false;
방문 한 곳과 벽인 곳이면 바로 false 리턴
위의 코드에 비해 함수 호출은 더 많아지지만 코드가 간결해진다.
boolean findPath(x,y)
if(x,y) is either on the wall or a visited cell
return false;
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;
미로찾기 자바 코드
- PATH_COLOR: visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell
- BLOCKED_COLOR: visited이며 출구까지의 경로상에 있지 않음이 밝혀진 cell
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,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; //white
private static final int WALL_COLOR = 1; //blue
private static final int BLOCKED_COLOR = 2; //red
private static final int PATH_COLOR = 3; //green
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_COLOR){
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;
return false;
}
}
public static void printMaze() {
for(int i =0; i< 8; i++) {
for(int j=0; j<8; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println("");
}
System.out.println("");
}
public static void main(String[] args){
printMaze();
findMazePath(0,0);
printMaze();
}