(Recursion) 미로 찾기

출처: 인프런-영리한 프로그래밍을 위한 알고리즘 강좌(권오흠 교수님)

위와 같은 그림의 미로가 있다고 할 때 입구에서 출구로 빠져나가기 위한 경로를 구하고자 한다면 어떠한 방법이 최선일까요? 2중 for문을 통해서 찾아갈 수도 있겠지만 이는 너무 어리석은 짓이고.. recursion을 통해 해결할 수 있을 겁니다. 먼저 recursion을 통해 해결하기 위한 base case를 보면 다음과 같습니다.

base case:

• 참조된 점 (x,y)가 이미 출구인 경우 
• 참조된 점 (x,y)가 벽인 경우

그렇다면 recursion case는 무엇일까요? 이는 참조되고 있는 자기 자신을 제외한 인접한 점들에 대하여 재귀적으로 함수를 호출하면 될것같습니다.

recursive case: 

• 인접한 4개의 점들에 대해 재귀적으로 검사

이번에는 단순히 true, false 형태로 출구로 빠져나올 수 있는 경로가 있는지 여부와 길만 표시하도록 하겠습니다. 먼저 위의 maze를 2중배열 형태로 각 상태에 따라 나타내보겠습니다.

public class Maze1 { private static int[][] grid = { {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 int N = 8; private static final int PATHWAY_COLOR = 0; // unvisited way private static final int WALL_COLOR = 1; // wall private static final int BLOCKED_COLOR = 2; // blocked way private static final int PATH_COLOR = 3; // right way (visited)

PATHWAY_COLOR는 아직 방문하지 않은 경로를 나타냅니다. 사실 위의 base case에서는 빠진 조건이 있는데 그것이 바로 cell의 방문 여부와 index가 범위를 벗어났는지를 체크하는 것입니다. 만약 cell의 방문여부를 검사하지 않는다면 recursion은 모든 인접한 cell에 대해 일어나는데 이전에 방문한 cell로 다시 참조되는 무한루프에 빠질 수도 있고, index를 검사하지 않는다면 IndexOutOfRange Exception이 발생할 것입니다. 이러한 무한루프를 막고자 이미 방문한 cell은 PATHWAY_COLOR로 값을 갱신할 것이고, 만약 인접한 모든 cell에 대해 검사 결과 모두 막혀있다면 그 cell을 block 처리할 것입니다. 아래는 수정된 base case와 recursion case 입니다.

base case:

• 참조된 점 (x, y)가 출구인 경우 : 점(x, y)를 PATH_COLOR로 update 후 return true
• 참조된 점 (x, y)가 배열의 범위를 벗어난 경우: false
• 참조된 점  (x, y)가 방문한 점이거나 벽인 경우: 점 (x, y)를 BLOCKED_COLOR로 update 후 false

recursion case:

• 점 (x, y)를 PATH_COLOR로 update 후, 인접한 4개의 점에 대해 재귀적으로 검사. 이 중 하나라도 true라면 true를 return. 그렇지 않다면 점(x, y)를 BLOCKED_COLOR로 update 후 false return.

다음은 완성된 코드입니다. 강의에 나온 테스트케이스만을 가지고 수행해봤기에 에러가 있을 수도 있습니다.

package recursion; /** * Created by junhyeok on 2017-07-08. */ public class Maze1 { private static int[][] grid = { {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 int N = 8; private static final int PATHWAY_COLOR = 0; // unvisited way private static final int WALL_COLOR = 1; // wall private static final int BLOCKED_COLOR = 2; // blocked way private static final int PATH_COLOR = 3; // right way (visited) public static void main(String[] args) { int x = 0, y = 0; System.out.println(findPath(y, x)); for (int i = 0; i <N; i++) { for (int j = 0; j < N; j++) { System.out.print(grid[i][j] + " "); } System.out.println(); } } static boolean findPath(int y, int x) { if (x == N - 1 && y == N - 1) { grid[y][x] = PATH_COLOR; // when exist return true; } else if (x < 0 || y < 0 || x > N - 1 || y > N - 1) { // out of index return false; } else if (grid[y][x] !=PATHWAY_COLOR) { // wall or visited cell return false; } else { grid[y][x]=PATH_COLOR; int[] xPos = {x - 1, x, x, x + 1}; int[] yPos = {y, y - 1, y + 1, y}; for (int i = 0; i < 4; i++) { if (findPath(yPos[i], xPos[i])) { return true; } } grid[y][x] = BLOCKED_COLOR; return false; } } }