-
[못풀었다/릿코드]2328. Number of Increasing Paths in a Grid코딩테스트 2023. 6. 18. 21:14
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를 잘 이용해야한다...
'코딩테스트' 카테고리의 다른 글
[릿코드/js] 605. can place flowers (0) 2023.09.13 [릿코드/js] 다시풀기 137.candy (0) 2023.09.13 [공부하고다시풀기../릿코드] 1187. Make Array Strictly Increasing (0) 2023.06.18 [못풀었다/릿코드] 1569. Number of Ways to Reorder Array to Get Same BST (0) 2023.06.16 [다시풀기/릿코드] 1161. Maximum Level Sum of a Binary Tree (0) 2023.06.15