[Programmers] 경주로 건설

2020 카카오 인턴 4번 문제였다.

맨처음 봤을땐 단순하게 백트래킹+가지치기로 접근하였다. 하지만 역시 N이 최대 25였기에 시간초과가 발생하였다. 그래서 다르게 접근을 해보았다. visit배열을 int로 정의하여서 각 지점마다 최소가 되는 값을 저장해주었고, 갱신이 가능할때만 그 지점으로 갈 수 있도록 DFS를 구현하여 풀었다. 일종의 DP 개념으로 접근하여 DFS를 해결하였다.

package programmers;
 
public class Solution_2020카카오인턴_경주로건설 {
    public static void main(String[] args) {
//        int[][] board= {
//                {0,0,0},
//                {0,0,0},
//                {0,0,0}
//        };
        int[][] board= {
                {0,0,1,0},
                {0,0,0,0},
                {0,1,0,1},
                {1,0,0,0}
        };
        
        System.out.println(solution(board));
    }
    
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    static int[][] visit;
    static int N;
    
    static int solution(int [][]board) {
        N=board.length;
        
        
        visit=new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++)
                visit[i][j]=Integer.MAX_VALUE/2;
        }
        
        visit[0][0]=0;
        for(int dir=0;dir<4;dir++) {
            int nextI=di[dir];
            int nextJ=dj[dir];
            
            if(nextI<0 || nextJ<0)
                continue;
            
            if(board[nextI][nextJ]==0) {
                dfs(board,nextI,nextJ,100,dir);
            }
        }
        
//        for(int i=0;i<N;i++) {
//            for(int j=0;j<N;j++) {
//                System.out.print(visit[i][j]+" ,");
//            }
//            System.out.println();
//        }
        
        return visit[N-1][N-1];
    }
    
    static void dfs(int[][] board,int i,int j,int sum,int curDir) {
        visit[i][j]=sum;
        
        if(i==N-1 && j==N-1) {
            return;
        }
        
        for(int dir=0;dir<4;dir++) {
            int nextI=i+di[dir];
            int nextJ=j+dj[dir];
            
            if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=N)
                continue;
            
            if(board[nextI][nextJ]==0) {
                if(dir==curDir && visit[i][j]+100 <= visit[nextI][nextJ]) {
                    dfs(board,nextI,nextJ,sum+100,dir);
                }else if(dir!=curDir && visit[i][j]+600 <= visit[nextI][nextJ]) {
                    dfs(board,nextI,nextJ,sum+600,dir);
                }
            }
            
        }
        
    }
    
}