[LeetCode] 329. Longest Increasing Path in a Matrix

😎풀이

1. 해당 좌표 및 값이 이동할 수 있는 셀인지 판별하는 isValid 선언
2. 깊이 우선 탐색을 실행하며 최대 길이를 반환하는 dfs 선언
3. O(n * m)을 반복하며 각 셀에서 발생할 수 있는 최대 길이를 확인
4. 최대 길이 반환

function longestIncreasingPath(matrix: number[][]): number {
    const rowMax = matrix.length
    const colMax = matrix[0].length
    let longest = 0
    const dp = Array.from({length: rowMax}, () => Array(colMax).fill(-1))
    const dy = [-1, 0, 1, 0]
    const dx = [0, 1, 0, -1]
    function isValid(row: number, col: number, prev: number) {
        if(row < 0 || row  >= rowMax) return false
        if(col < 0 || col >= colMax) return false
        if(prev >= matrix[row][col]) return false
        return true 
    }
    function dfs(row: number, col: number) {
        if(dp[row][col] !== -1) return dp[row][col]
        const curVal = matrix[row][col]
        let maxLength = 1
        for(let i = 0; i < 4; i++) {
            const ny = row + dy[i]
            const nx = col + dx[i]
            if(isValid(ny, nx, curVal)) maxLength = Math.max(maxLength, dfs(ny, nx) + 1)
        }
        dp[row][col] = maxLength
        return maxLength
    }
    for(let row = 0; row < rowMax; row++) {
        for(let col = 0; col < colMax; col++) {
            longest = Math.max(longest, dfs(row, col))
        }
    }
    return longest
};