재귀함수 공부하기.. (feat. 미로찾기)

재귀함수를 공부하는데 유튜브의 권오흠교수님의 강의를 보면서 공부를 했다.

 

재귀함수를 만들려면 노하우가 암시적 매개변수를 명시적 매개변수로 바꾸라! 라고 하셨다.

 

이번 미로 찾기 문제는 미로가 주어지고 거기까지의 경로를 구하는 문제였는데, 힌트 한번보고 재밌게 풀었다..

 

import java.util.Stack;

public class Test {
    public static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {

        boolean[][] board = {{true,true,true,true,true,true,true,false},{true,false,false,true,false,false,true,false},
                {true,true,true,false,true,true,true,false},{true,false,true,true,false,false,true,true}
        ,{true,false,false,false,true,true,false,false},{true,false,true,true,true,false,true,false},
                {true,true,true,false,true,true,true,false},{true,false,false,false,true,false,true,true}};

        boolean[][] clone = board.clone();

        Stack<String> stack = new Stack<>();
        recur(board,clone,0,0, board.length,stack);

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

    public static boolean recur(boolean[][] board,boolean[][] clone, int x, int y, int n,Stack<String> stack) {
        if (x == n - 1 && y == n - 1) {
            stack.push(x + " " + y + "\n 출구입니다");
            return true;
        } else if (x < 0 || y < 0 || x > n - 1 || y > n - 1 || !clone[y][x]) {
            return false;
        }
        
        clone[y][x] = false;
       
        for (int[] direction : dir) {
            if (recur(board,clone, x + direction[0], y + direction[1],n,stack)) {
                stack.push(x + " " + y);
                return true;
            }
        }
        
        clone[y][x] = true;
        return false;
    }
}

다풀고나서 든 생각이지만 굳이 clone을 만들어서 쓸 필요가 없는 것 같다.

어차피 다시 방문했던곳을 true로 풀어주기 때문에 빼버려도 될 것 같다.

 

그 외에는 board를 boolean이 아닌 숫자로 해서 값 별로 의미를 정해두는 것도 나쁘지 않을 것 같다.