LEETCODE 329 : Longest Increasing Path in a Matrix - python

Q. 문제

ttps://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Longest Increasing Path in a Matrix - LeetCode

A. 풀이

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        result = 0
        visit = [[1]*len(matrix[0]) for _ in range(len(matrix))]
        
        def dfs(x, y, n):   
            ans = n
            for d in range(4):
                tx = x + dx[d]
                ty = y + dy[d]
                if tx < 0 or ty < 0 or tx >= len(matrix) or ty >= len(matrix[0]):
                    continue
                if matrix[tx][ty] > matrix[x][y] and visit[tx][ty] <= visit[x][y] + 1:
                    visit[tx][ty] = visit[x][y] + 1
                    ans = max(dfs(tx, ty, n + 1), ans)
            return ans
                    
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                result = max(dfs(i, j, 1), result)
        return result

가장 긴 증가 길이 찾기

일종의 동적 계획법인데 루트를 추적하는게 dfs의 재귀를 이용해서 풀었다.

 

1) visit 배열에 해당 위치에서 가질 수 있는 길이를 저장 

2) 더 작은 방문일 경우에는 검사하지 않도록 제외시킴 -> 시간 단축