[08] 순환함수 ( 재귀함수 ) - JAVA로 미로찾기 문제 구현

 

MAZE 예시

 

public class maze {
	static int size = 8; // 미로는 size X size 크기 
	static int visited =2;  // visited : 방문한 길 표시
	static int cannot =3; // cannot : 막혀있는 길 표시 -> 동서남북 다 보더라도 벽이거나 왔던 길밖에 없어서 새로운 길로 가지 못하는 경우
	public static void main(String[] args) {
		int[][] maze= { // 0은 길, 1은 벽
				{0,0,0,0,1,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},
		};
		
		System.out.println(findPath(maze, 0, 0)); // 0,0 에서 출발시 길이 있으면 true , 없으면 false 출력
	
		
	}
	
	public static boolean findPath(int[][] maze,int x, int y) {
		if(x<0 || y<0 || x>=size || y>=size) return false;
		else if(maze[x][y]!=0) return false; // 새로 온 길이 아니라면 false
		else if(x==size-1 && y==size-1) { // 여기가 출구인 경우
			maze[x][y]=visited;
			return true;
		}
		else {
			maze[x][y]=visited;
			if(findPath(maze, x, y+1) || findPath(maze, x-1, y)||findPath(maze, x, y-1)||findPath(maze, x+1, y)) // 동서남북 길에대해서 재귀로 함수 호출
			{
				return true;
			}
			else{ // 동서남북 길에대해서 갈 곳이 없으면
				maze[x][y]=cannot;
				return false;
			}
		}

		
	}

}