[프로그래머스] Level3 - 경주로 건설(2020 카카오 인턴십)

class Solution {
    static boolean check(int x, int y, int[][] map){
	    if(x>=0 && y>=0 && x<map.length && y<map[x].length) return true;
	    else return false;
	}
		static int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int M;
    static int[][] memo;
    static public int solution(int[][] board) {
        M = board.length;
        memo = new int[M][M];
        boolean[][] visit = new boolean[M][M];
        
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++) memo[i][j] = Integer.MAX_VALUE;
        }
        
        visit[0][0] = true;
        dfs(0,0,-1,0,board,visit);
        
        return res;
    }
    static int res = Integer.MAX_VALUE;
    static void dfs(int x, int y, int direction, int val, int[][] board, boolean[][] visit) {
        if(x == M-1 && y == M-1) {
            if(res > val) res = val;
            return;
        }
        if(res < val) return;
        if(memo[x][y] < val) return;
        int dx, dy;
        for(int d=0; d<4; d++){
            dx = x + dir[d][0];
            dy = y + dir[d][1];
            if(check(dx,dy,board) && board[dx][dy] == 0 && !visit[dx][dy]){
                visit[dx][dy] = true;
                if(d==direction || direction == -1){
                    if(memo[dx][dy] >= val + 100){
                        memo[dx][dy] = val+100;
                        dfs(dx,dy,d,val+100,board,visit);
                    }
                }else {
                    if(memo[dx][dy] >= val + 600){
                        memo[dx][dy] = val+600;
                        dfs(dx,dy,d,val+600,board,visit);
                    }
                }
                visit[dx][dy] = false;
            }
        }
    }
}