[LeetCode] 329 | Longest Increasing Path in a Matrix | Python

---

문제 링크: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

---

문제

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

---

조건

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= $2^{31}$ - 1

---

내 풀이

dfs를 이용한다.

현재 위치([y][x])보다 neighbor의 위치([newY][newX])가 더 큰 방향으로 이동해간다.

그러면서 현재까지의 거리를 업데이트한다.

---

코드

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        H, W = len(matrix), len(matrix[0])
        dist = defaultdict(int)
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        def dfs(y, x):
            if (y, x) in dist:
                return dist[(y, x)]
            
            cur_dist = 1
            for t in range(4):
                newY, newX = y+dy[t], x+dx[t]
                
                if 0<=newY<H and 0<=newX<W and matrix[y][x] < matrix[newY][newX]:
                    cur_dist = max(cur_dist, dfs(newY, newX)+1)
            
            dist[(y, x)] = cur_dist
            return cur_dist
        
        ans = 1
        for h in range(H):
            for w in range(W):
                ans = max(ans, dfs(h, w))
                
        return ans