329. Longest Increasing Path in a Matrix - Streak 13

현재 위치에서 가장 긴 경로는 과거에 영향을 받지 않는다.
가장 긴 경로는 오직 현재 위치의 숫자에만 영향을 받는다.

 

그러니 DP로 설계 가능하다.

 

탑-다운 + DP의 형식으로 풀 수 있는데,
독특한 점은 "더 작은 수일때만 함수를 호출한다"는 제약조건을 통해 무한루프를 막는다는 점이다.

class Solution {
    static int[] dx = new int[]{-1, 1, 0, 0};
    static int[] dy = new int[]{0, 0, -1, 1};
    public int longestIncreasingPath(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        int ans = 0;
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++)
                ans = Math.max(ans, dfs(i, j, dp, matrix));
        }
        return ans;
    }

    private int dfs(int x, int y, int[][] dp, int[][] matrix){
        if(dp[x][y] != 0) return dp[x][y];
        int n = matrix.length;
        int m = matrix[0].length;
        int ret = 1;
        for(int k = 0; k<4; k++){
            int p = x + dx[k], q = y + dy[k];
            if(p < 0 || p >= n || q < 0 || q >= m) continue;
            if(matrix[x][y] >= matrix[p][q]) continue;
            ret = Math.max(ret, 1 + dfs(p, q, dp, matrix));
        }
        return dp[x][y] = ret;
    }

}

record Idx(int x, int y, int val)  implements Comparable<Idx>{
    @Override
    public int compareTo(Idx o){
        return this.val - o.val;
    }
}

 

조금 느린 풀이로는, O(nlogn)도 가능할 듯 하다.
(위 특성을 이용해, 정렬 후 작은 숫자부터 순회하는 방식이다.)