[프로그래머스] 게임 맵 최단거리

 - 실패 코드

 - dfs 로 시도

 - dfs 로 시도할 경우 재귀가 너무 오래 돌아서 돌다가 timeover

 

class Solution {
    private int min;
    private int n;
    private int m;
    class Cell {
        private int x;
        private int y;
        
        public Cell(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        private int getX() {
            return this.x;
        }
        
        private int getY() {
            return this.y;
        }
        
        private boolean isCompleted() {
            return this.x == n-1 && this.y == m-1;
        }
        
        private void move(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        private boolean canMove(int x, int y, int[][] maps, boolean[][] visited) {
            return visited[x][y] == false && x >= 0 && y >= 0 && x < n && y < m && maps[x][y] > 0;
        }
    }
    
    private void dfs(Cell cell, int[][] maps, int count, boolean[][] visited) {
        int x = cell.getX();
        int y = cell.getY();
        if(!cell.canMove(x, y, maps, visited)) {
            return;
        }
        // System.out.println("n : " + n);
        // System.out.println("m : " + m);
        // System.out.println("x : " + x + " y : " + y);
        if(cell.isCompleted()) {
            // System.out.println("count :" + count);
            if(min > count) min = count;
            return;
        }
        visited[x][y] = true;
        cell.move(x, y-1);
        dfs(cell, maps, count+1, visited);
        cell.move(x, y+1);
        dfs(cell, maps, count+1, visited);
        cell.move(x-1, y);
        dfs(cell, maps, count+1, visited);
        cell.move(x+1, y);
        dfs(cell, maps, count+1, visited);
        visited[x][y] = false;
        
    }
    public int solution(int[][] maps) {
        this.n = maps.length;
        this.m = maps[0].length;
        int maxCellValue = n*m +1;
        this.min = maxCellValue;
        boolean[][] visited = new boolean[n][m];
        int x = 0;
        int y = 0;
        Cell cell = new Cell(x, y);
        dfs(cell, maps, 1, visited);
        return min == maxCellValue ? -1 : min;
    }
}