Recursion의 응용 [미로찾기1]

※ 재귀함수를 이용한 미로찾기

 - 재귀함수를 이용하여 위의 미로의 형태에서 출구를 찾는 알고리즘을 구현 한다.

 - 문제에서는 findExit 메소드의 리턴값을 boolean으로 두고 출구가 있느냐 없느냐를 true, false로 나타내는데서 끝냈지만

   개인적으로 탐색한 경로를 알고싶어서 아래와 같은 식으로 구현했다.

public class mazeEx {

       

       private static int PATH_WAY = 0;

       private static int WALL = 1;

       private static int VISITED_WAY =2;

       private static int EXIT = 3;

       private static boolean IS_ESCAPE = false;

       

       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, 3 }

              };

       

       public static void main(String[] args) {

              

              int xIdx=0;

              int yIdx=0;

              

              findExit(xIdx, yIdx);

              

              if(IS_ESCAPE){

                     System.out.println("출구 발견!!");

                     printMaze();

              }else{

                     System.out.println("출구가 없습니다...ㅜㅜ");

                     printMaze();

              }

       }

       

       private static void findExit(int xIdx, int yIdx){

                 

              if(xIdx < 0 || xIdx > 7 || yIdx < 0 || yIdx > 7){

              return;

              }else if(IS_ESCAPE == true){

                    return;

              }else if(MAZE[xIdx][yIdx] == EXIT){

                    IS_ESCAPE = true;

                    return;

              }else if(MAZE[xIdx][yIdx] == VISITED_WAY || MAZE[xIdx][yIdx] == WALL){

                    return;

              }else{

             MAZE[xIdx][yIdx] = VISITED_WAY;

                    findExit(xIdx+1, yIdx);

                    findExit(xIdx-1, yIdx);

                    findExit(xIdx, yIdx+1);

                    findExit(xIdx, yIdx-1);

              }// else end

       }// function end

       

       public static void printMaze(){

              

              for(int i = 0; i < MAZE.length; i++){

                     for(int j = 0; j<MAZE[i].length; j++){

                           System.out.print(MAZE[i][j]);

                           if(j != MAZE[i].length-1){

                                  System.out.print(", ");

                           }

                     } //inner for end

                     

                     System.out.println();

       

              } //outer for end

              

       }// function end

       

}

※ 결과화면

 - 위의 미로를 탐색했을 때..

 - 임의로 출구에 도달하지 못하게 미로를 변경했을 때..