2023.06.18 Today's Challenge

fabichoi 2023. 6. 18. 23:45

https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/

Number of Increasing Paths in a Grid - LeetCode

Can you solve this real interview question? Number of Increasing Paths in a Grid - You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions. Return the number of strictly increasing paths in the gr

leetcode.com

DFS + sort 로 푸는 문제

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        mod = 10 ** 9 + 7
        directions = [[0,1], [0,-1], [1,0], [-1,0]]

        dp = [[1] * n for _ in range(m)]

        clist = [[i,j] for i in range(m) for j in range(n)]
        clist.sort(key=lambda x: grid[x[0]][x[1]])

        for i, j in clist:
            for di, dj in directions:
                ci, cj = i + di, j + dj
                if 0 <= ci < m and 0 <= cj < n and grid[ci][cj] > grid[i][j]:
                    dp[ci][cj] += dp[i][j]
                    dp[ci][cj] %= mod
        
        return sum(sum(row) % mod for row in dp) % mod