1-1. 재귀함수 - 미로찾기

1. 문제 설명

 출발 좌표를 임의로 지정해주었을 때, 탈출이 가능한지 확인하는 문제이다.

 미로에는 검은색 벽이 존재한다. (입력 시, 1은 벽을 의미하고, 0은 이동이 가능한 길을 의미) 

2. Java 구현

package recursive;

public class FindMaze {
    public static void main(String[] args) {
        /* 1 : 벽, 0 : 이동 가능 통로 */
        int[][] maze = {
                {0, 0, 0, 0, 0, 0, 0, 0},
                {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}
        };

        boolean[][] visited = new boolean[maze.length][maze[0].length];

        int startX = 0;
        int startY = 0;

        int finX = 7;
        int finY = 7;

        System.out.println(findMaze(startX, startY, finX, finY, visited, maze) ? "탈출 가능!" : "탈출 불가!");
    }

    public static boolean findMaze(int nowX, int nowY, int finX, int finY, boolean[][] visited, int[][] maze) {
        if(visited[nowX][nowY] || maze[nowX][nowY] == 1) {
            return false;
        } else if(nowX == finX && nowY == finY) {
            return true;
        } else {
            visited[nowX][nowY] = true;
            System.out.println("X, Y --> " + nowX + " , " + nowY);
            if(nowX > 0 && findMaze(nowX - 1, nowY, finX, finY, visited, maze)) {
                return true;
            }
            if(nowX < maze[0].length - 1 && findMaze(nowX + 1, nowY, finX, finY, visited, maze)) {
                return true;
            }
            if(nowY > 0 && findMaze(nowX , nowY - 1, finX, finY, visited, maze)) {
                return true;
            }
            if(nowY < maze[0].length - 1 && findMaze(nowX, nowY + 1, finX, finY, visited, maze)) {
                return true;
            }
        }
        return false;
    }
}

3. Paint Point

 미로 찾기를 재귀를 통해 구현했다. 백준 Q2667을 풀기위한 준비운동이라고 생각하면 될거같다. 근데 문제를 풀면서 느낀건데, 준비운동하다가 에너지를 

 다 소비했다. 백준 Q2667 보다 재귀에 가깝게 구혀하였다. 재귀에 더 가깝다고 생각한 이유는, 두 가지이다. 첫 번째는 문제를 작게 쪼개는 과정이 있었고,

 두 번째는 종료조건이 명확하게 있기 때문이다. 종료조건이 명확하게 되있지 않으면, 재귀함수는 계속해서 스택에 쌓이게 되고, 프로그램이 종료된다.

 재귀에서 가장 중요한 것은 종료조건을 명확하게 명시!