[Lv.3] 경주로 건설

import java.util.Arrays;

class Solution {
    static int n;
    static int minCost;

    static int[][] gameBoard;
    static boolean[][] visit;
    static int[][][] costDp;
    public int solution(int[][] board) {
        n=board.length;
        minCost=Integer.MAX_VALUE;
        gameBoard=board.clone();
        visit=new boolean[gameBoard.length][gameBoard.length];
        costDp=new int[gameBoard.length][gameBoard.length][2];
        for (int[][] ints : costDp) {
            for (int[] anInt : ints) {
                anInt[0]=anInt[1]=Integer.MAX_VALUE;
            }
        }
        //way : 1= Up,Down -1: Left,Right
        costDp[0][0][0]=costDp[0][0][1]=0;
        dfs(0,0,0,0);
        return minCost;
    }
    private void dfs(int i,int j, int cost,int way){
        if (i == n - 1 && j == n - 1) {
            minCost=Math.min(minCost,cost);
            return;
        }
        if(cost>minCost)
            return;

        //
        if(costDp[i][j][0]<cost&&costDp[i][j][1]<cost)
            return;

        if(i>0&&!visit[i-1][j]&&gameBoard[i-1][j]==0){
            //Go Up
            if(way==1 || way==0){
                //코너 없이 직선
                cost+=100;
                visit[i][j]=true;
                costDp[i-1][j][0]=Math.min(costDp[i-1][j][0],cost);
                dfs(i-1,j,cost,1);
                visit[i][j]=false;
                cost-=100;
            }else{
                //코너 생성 필요 (직전 움직임이 좌,우 였다)
                cost+=600;
                visit[i][j]=true;
                costDp[i-1][j][1]=Math.min(costDp[i-1][j][1],cost);
                dfs(i-1,j,cost,1);
                visit[i][j]=false;
                cost-=600;
            }
        }
        if(i<n-1&&!visit[i+1][j]&&gameBoard[i+1][j]==0){
            //Go Down
            if(way==1 || way==0){
                //코너 없이 직선
                cost+=100;
                visit[i][j]=true;
                costDp[i+1][j][0]=Math.min(costDp[i+1][j][0],cost);
                dfs(i+1,j,cost,1);
                visit[i][j]=false;
                cost-=100;
            }else{
                //코너 생성 필요 (직전 움직임이 좌,우 였다)
                cost+=600;
                visit[i][j]=true;
                costDp[i+1][j][1]=Math.min(costDp[i+1][j][1],cost);
                dfs(i+1,j,cost,1);
                visit[i][j]=false;
                cost-=600;
            }
        }
        if(j>0&&!visit[i][j-1]&&gameBoard[i][j-1]==0){
            //Go Left
            if(way==-1 || way==0){
                cost+=100;
                visit[i][j]=true;
                costDp[i][j-1][0]=Math.min(costDp[i][j-1][0],cost);
                dfs(i,j-1,cost,-1);
                visit[i][j]=false;
                cost-=100;
            }else{
                cost+=600;
                visit[i][j]=true;
                costDp[i][j-1][1]=Math.min(costDp[i][j-1][1],cost);
                dfs(i,j-1,cost,-1);
                visit[i][j]=false;
                cost-=600;
            }
        }
        if(j<n-1&&!visit[i][j+1]&&gameBoard[i][j+1]==0){
            if(way==-1 || way==0){
                cost+=100;
                visit[i][j]=true;
                costDp[i][j+1][0]=Math.min(costDp[i][j+1][0],cost);
                dfs(i,j+1,cost,-1);
                visit[i][j]=false;
                cost-=100;
            }else{
                cost+=600;
                visit[i][j]=true;
                costDp[i][j+1][1]=Math.min(costDp[i][j+1][1],cost);
                dfs(i,j+1,cost,-1);
                visit[i][j]=false;
                cost-=600;
            }
        }

    }
}

---

처음엔 DFS로만 구현했는데, 제출해보니 시간초과가 났다.

그래서, 2차원 dp를 섞어서 해당 노드까지의 비용이 저장된 비용보다 큰 경우 탐색을 종료하는 로직을 추가했더니, 2개의 테스트 케이스에서 실패가 떴다.

코너를 통해 들어온 경우에 코너를 통하지 않은 경로보다 비용이 당장은 비싸지만 향후 경로에서 이득인 경우가 발생할 수 있기 때문에 3차원dp를 만들어 비용을 검사하는 로직을 추가했다.

결과는, 무난하게 통과되었다 !