순환적으로 생각하기
현재 위치에서 출구까지 가려면 아래와 같이 두 가지 중 하나의 조건을 만족해야한다.
1.
현재 위치가 이미 출구이거나
2.
현재 위치와 이웃한 셀에서 현재 위치를 지나치지 않고 출구까지 가는 경로가 있거나
즉 여기에도 순환적인 개념이 바로 드러나는데, 현재 위치에서 출구까지 가는 방법에 대해 현재 위치와 이웃한 셀에서 출구까지 가는 방법을 조사하는 것으로부터 알 수 있다는 점이다.
package practice.algorithm.recursion;/** * 미로찾기 * */public class Maze { private static final 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, 1}, {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_COLOR = 0; private static final int WALL_COLOR = 1; private static final int BLOCKED_COLOR = 2; private static final int PATH_COLOR = 3; public static void main(String[] args) { printMaze(); findMazePath(0, 0); printMaze(); } private static void printMaze() { for (int i = 0; i < maze.length; i++) { for (int j = 0; j < maze.length; j++) { System.out.print(maze[i][j]); } System.out.println(); } System.out.println(); } public static boolean findMazePath(int x, int y) { //범위를 벗어나는 경우 if (x < 0 || y < 0 || x >= N || y >= N) { return false; } //통로 색이 아닌 경우 if (maze[x][y] != PATHWAY_COLOR) { return false; } //마지막 출구 좌표인 경우 if (x == N-1 && y == N-1) { maze[x][y] = PATH_COLOR; return true; } maze[x][y] = PATH_COLOR; if (findMazePath(x-1, y) || findMazePath(x+1, y) || findMazePath(x, y-1) || findMazePath(x, y+1)) { return true; } maze[x][y] = BLOCKED_COLOR; return false; } /** * 00000001 * 01101101 * 00010001 * 01001101 * 01110011 * 01000101 * 00010001 * 01110100 * * 30000001 * 31101101 * 30010001 * 31001101 * 31112211 * 31333121 * 33313331 * 21112133 * */}
Java
복사