[못풀었다/릿코드]2328. Number of Increasing Paths in a Grid

var countPaths = function(grid) {
    //increasing
    //일단 셀별로 하나씩
    //두개.. 세개 네개.. 나아가는 것이 좋겠음.
    //adjacent 즉 인접한 곳만 갈 수 있음.
    //인접한 곳으로 가면서, 4방향중에 증가된 곳은 가고 증가되지 않은 곳은 안갈것.
    //가면 일단 간것으로 1추가하고, 그 다음으로 갈 수 있는지 확인해서 또 1추가.
    //일단 전체를 한바퀴 돌아야함.
    const MOD = 1e9 + 7;
    const dx = [1,-1,0,0];
    const dy = [0,0,1,-1];
    const m = grid.length;
    const n = grid[0].length;
    let answer = 0;
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            let startCellIdx = [i,j]
            let queue = [startCellIdx];
            while(queue.length){
                (answer++)%MOD
                let [y,x] = queue.shift();
                for(let k=0;k<4;k++){
                    let nextX = x+dx[k]
                    let nextY = y+dy[k]
                if(nextX>=0&&nextX<n&&nextY>=0&&nextY<m&&grid[nextY][nextX]>grid[y][x]){
                    queue.push([nextY,nextX])
                }
            }
            }
            
        }
    }
    return (answer)%MOD
    
};

처음 풀었던 풀이. 안풀리는 것은 아니었으나 시간복잡도에서 막혔음.

 

var countPaths = function(grid) {
  let mod = Math.pow(10, 9) + 7;
  let result = 0;
  let rows = grid.length, columns = grid[0].length;
  let dp = Array(rows).fill(null).map(_ => Array(columns).fill(0));
  
  const dfs = (r, c, preVal)=> {
    if (r < 0 || r == rows || c < 0 || c == columns || grid[r][c] <= preVal) return 0
    if (dp[r][c]) return dp[r][c]
    return dp[r][c] = (1 + dfs(r + 1, c, grid[r][c]) + 
                       dfs(r - 1, c, grid[r][c]) + 
                       dfs(r , c + 1, grid[r][c]) +  
                       dfs(r , c - 1, grid[r][c])) % mod;
  }
   for(let i = 0; i < rows; i++) {
    for(let j = 0; j < columns; j++) {
      result += dfs(i, j, -1) % mod;
    }
  }
 
  return result % mod;
};

이후 dp를 이용한 풀이. dp를 잘 이용해야한다...