[Algorithm] 순환 ④

< 미로 찾기 문제 >

=> Recursive Thinking : 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

 

- 미로 찾기 예시

Decision Problem(답이 yes 또는 no인 문제)으로 전환 

Ex) 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;

=> 무한루프에 빠지는 경우가 생김으로 수정해야함.

 

Ex) 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;

=> 방문한 곳과 방문하지 않은 곳을 나누어 무한루프에 빠지지 않도록 설계함.

 

- 최종적으로 구현할 것 ( 위의 코드보다 recursion의 횟수는 많아지지만 코드는 간결해짐 )

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;

 

- 미로 정의 & 실제 사용

Ex) 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, 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_COLOUR = 0 ; // white 통로

      private static final int WALL_COLOUR = 1 ; // blue 벽

      private static final int BLOCKED_COLOUR = 2 ; // red 이미 방문해본 곳

      private static final int PATH_COLOUR = 3 ; // green 아직 모르는 곳

 

=> PATH_COLOR : visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell

=> BLOCKED_COLOR : visited이며 출구까지의 경로상에 있지 않음이 밝혀진 cell

 

    public static boolean findMazePath ( int x, int y ) {

         if ( x < 0 || y < 0 || x >= N || y >= N )

            return false ;  // 미로의 범위 바깥은 flase를 return

         else if ( maze [ x ] [ y ] != PATHWAY_COLOUR )

            return false ;  // green, red, blue인 경우 false를 return

         else if ( x == N-1 && y == N-1 ) {

            maze [ x ] [ y ] = PATH_COLOUR ;

            return true ; // 출구이므로 true를 return

         }  

 

         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 ; // 북, 동, 남, 서의 4가지 방향을 경로를 탐색

                }

                maze [ x ] [ y ] = BLOCKED_COLOUR ; 

                return false ; 

         }

    }

 

public static void main ( String [ ] args ) {

     printMaze ( ) ;

     findMazePath ( 0, 0 ) ;

     printMaze ( ) ; } }