329. Longest Increasing Path in a Matrix

leetcode.com/problems/longest-increasing-path-in-a-matrix/

Longest Increasing Path in a Matrix - LeetCode

문제:

오름차순으로 가장 긴 루트를 찾는 문제

 

접근법:

DFS + DP + 백트래킹

 

풀이:

완전탐색으로 DFS로 풀면 시간초과가 난다.

 

따라서 나는 DP를 선택했다. 

 

그럼에도 불구하고 마지막 테스터케이서 4개에서 시간초과가 났다. 따라서 백트래킹도 추가했다.

 

코드:

class Solution {
    static int dp[][];
    static int wide, height;
    static int dr[] = {-1,1,0,0};
    static int dc[] = {0,0,-1,1};
    public int longestIncreasingPath(int[][] matrix) {
        wide = matrix[0].length;
        height = matrix.length;
        dp = new int[height][wide];
        for(int i=0; i<height; i++){
            Arrays.fill(dp[i], 1);
        }
        for(int i=0; i<height; i++){
            for(int j=0; j<wide; j++){
                if(dp[i][j]==1){
                    dfs(matrix, i, j);
                }
            }
        }
        int answer = 0;
        for(int i=0; i<height; i++){
            for(int j=0; j<wide; j++){
                answer=Math.max(answer, dp[i][j]);
            }
        }
        
        return answer;
    }
    static void dfs(int[][] matrix, int r, int c){
        for(int k=0; k<4; k++){
            int nr = r+dr[k];
            int nc = c+dc[k];
            if(nr<0||nr>=height||nc<0||nc>=wide||matrix[nr][nc]<=matrix[r][c])
                continue;
            int tmp = dp[r][c]+1;
            if(tmp > dp[nr][nc]){
                dp[nr][nc] = tmp;
            }else{
                continue;
            }
            dfs(matrix, nr, nc);
        }
    }
}