[Algorithm] 2-4. Recursion 응용 1 - 미로찾기 Java 구현

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

2-4. Recursion의 응용 1 - 미로찾기

Maze - 미로찾기

• (n-1, n-1)의 좌표를 출구로 가정

• 흰색이 지날 수 있는 길, 파란색이 벽

• 입구에서 출구까지의 경로를 찾는 문제

Recursive Thinking

• 현재 위치에서 출구까지 가는 경로가 있으려면

  • 현재 위치가 출구이거나(이미 내가 출구에 와 있거나). 혹은,

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

    • 위의 경우를 Recursive하게 생각한다. 전체 문제를 해결하려고 하면 부분 문제의 해결이 이루어 지면서 전체 문제가 해결된다.

  • 위의 둘중에 하나가 성립해야 출구까지 가는 경로가 있다고 할 수 있다.

미로찾기(Decision Problem) - 답이 Yes or No인 문제

• 출발점에서 출구까지 가능 경로가 있느냐 없느냐? 의 문제로 생각한다.

• x', y'는 현재 셀과 이웃한 셀들

  • x, y의 x', y'(4개)를 각각 봤을 때, pathway가 없다면 출구까지 가는 경로가 없다.

• recursion을 고민할 때, 가장 먼저 고민할 것은 무한 루프에 빠지지 않는가 이다.

  • Base case로 수렴하는가를 확인해야한다.

  • 현재 아래 코드에서는 pathway인 인접한 두 셀끼리의 무한루프가 발생할 수 있다.(서로가 서로의 x', y'가 될 수 있으므로)

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;

• 따라서, x, y의 상황에서 고려할 때 x', y'에서 다시 x, y로 돌아오는 것을 막아줄 필요가 있다.

  • 그것을 방문한 위치와 방문하지 않은 위치로 구분하여 처리한다.

  • 아래와 같이 코드가 변경될 수 있다.

  • 조건문에서 pathway체크와 함께 방문하지 않은 셀의 여부를 체크하기 때문에 무한 루프에 빠지지 않는다.

  
  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 호출(finfPath(x', y'))을 하기전에 pathway체크와 방문여부를 체크하지 않고, 메소드의 시작지점에서 pathway체크와 방문여부를 체크하여 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;

Maze - Java 구현

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

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

• 일단 방문하면 PATH COLOR로 칠하고, 출구까지의 경로상에 있지 않음이 밝혀질 경우 BLOCKED_COLOR로 칠한다.

public class Maze {
  private static final int PATHWAY_COLOR = 0;
  private static final int WALL_COLOR = 1;
  private static final int BLOCKED_COLOR = 2;
  private static final int PATH_COLOR = 3;
  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}
  };
​
  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 main(String[] args) {
    printMaze();
    findMazePath(0, 0);
    System.out.println();
    printMaze();
  }
​
  private static void printMaze() {
    for (int x = 0; x < N; x++) {
      System.out.print("{");
      for (int y = 0; y < N; y++)
        System.out.print(maze[x][y] + ", ");
      System.out.println("}");
    }
  }
}

{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, }
​
{3, 2, 2, 2, 2, 2, 2, 1, }
{3, 1, 1, 2, 1, 1, 2, 1, }
{3, 2, 2, 1, 2, 2, 2, 1, }
{3, 1, 2, 2, 1, 1, 2, 2, }
{3, 1, 1, 1, 2, 2, 1, 1, }
{3, 1, 3, 3, 3, 1, 2, 1, }
{3, 3, 3, 1, 3, 3, 3, 1, }
{0, 1, 1, 1, 0, 1, 3, 3, }
​
Process finished with exit code 0