[Recursion] 미로 찾기

미로 찾기 (Decision Problem)

미로찾기 해결 알고리즘 중에 Recursion을 이용한 것이 가장 간명하다.

Decision Problem  :  답이 yse or no인 문제

Recursive Thinking

• 현재 위치가 출구인가? 아니면,

• 이웃한 셀들 중 현재 위치를 지나지 않고 출구까지 가는 경로가 있다.




현재 위치에서 출구까지의 경로
이웃한 셀들 중에서 출구까지 가능 경로 찾기

Recursion을 설계할 때는 "무한루프에 빠지지 않는가?"를 가장 먼저 생각해야 한다.

[ 위치 x,y로 부터 출구까지 가는 경로가 있는지 판단하는 함수 ]

findPath
수도 코드

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;
}

• 이미 방문한 셀들은 표시하기
• 인접한 셀들 중에 나를 다시 통하지 않고 출구로 가는 경로가 있는지 판단한다.
• 인접한 셀이 벽인지 아닌지도 판단, 통로가 아닌 경우면 무시한다.

< 다른 방식 >

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;
}

findMazePath
java 코드

// PATHWAY_COLOUR 통로 
// WALL_COLOUR 벽 
// BLOCKED_COLOUR 더 이상 길이 없는 셀 
// PATH_COLOUR 방문한 셀 
 
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) // 길이 아닌 경우 
    return false;
  else if ( x==N-1 && y==N-1){
    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;
     return false;
  }
}

출처

https://www.youtube.com/watch?v=m6lXDsx7oCk&index=4&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l