329. Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix - LeetCode

양의 정수로 구성된 2차원 배열이 주어진다.

2차원 배열의 임의의 인덱스 (i, j)에서 시작해 현재 인덱스가 가리키는 값 보다 큰 값으로만 4방 이동할 수 있다고 가정할 때, 이동할 수 있는 최대 거리의 길이를 반환하는 문제다.

 

예시

최대 길이는 4

최대 길이는 4

1. DFS + DP

from typing import *


class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:

        height, width = len(matrix), len(matrix[0])
        cache = [[0] * width for _ in range(height)]
        xpo, ypo = [0, 0, 1, -1], [1, -1, 0, 0]
        answer = 0

        def dfs(cx, cy):
            cache[cx][cy] = 1

            for p in range(4):
                nx, ny = cx + xpo[p], cy + ypo[p]
                if 0 <= nx < height and 0 <= ny < width:
                    if matrix[nx][ny] > matrix[cx][cy]:
                        if not cache[nx][ny]:
                            cache[cx][cy] = max(cache[cx][cy], dfs(nx, ny) + 1)
                        else:
                            cache[cx][cy] = max(cache[cx][cy], cache[nx][ny] + 1)
            return cache[cx][cy]

        for i in range(height):
            for j in range(width):
                if not cache[i][j]:
                    answer = max(answer, dfs(i, j))

        return answer

Tree DP라는 알고리즘이 있는데 그런 유형의 문제인데 트리 등의 자료구조를 순회하면서 하면서 DP 테이블을 만들게 된다.

우리가 원하는 답을 얻기 위해 의식의 흐름 기법(?)을 사용해보면 아래와 같다.

• 우리가 원하는 값은 어떤 지점에서 뻗어나갈 수 있는 최대 길이의 값이다.
  • 이걸 빠르게 구하면 더 좋다.
• 어떤 지점 A에서 어떤 지점 B로만 이동할 수 있다면, 어쩐 지점 A에서 뻗어나갈 수 있는 최대 길이는 어떤 지점 B에서 뻗어나갈 수 있는 최대길이 +1이다.
• 이걸 일반화하면 임의의 지점 A에서 뻗어나갈 수 있는 최대 길이는 A에서 바로 이동할 수 있는 4방에 위치한 지점들에서 뻣어나갈 수 있는 최대 길이들의 최댓값 + 1이다.
  • 이 부분에서 DP가 사용된다.

cache라는 2차원 배열을 방문 배열 + DP 값 저장 배열로 사용한다.

이동 조건에 부합하면 DFS를 타고 그 DFS에서 얻어지는 값을 반환하면서 최댓값을 갱신시키는 식으로 문제를 해결할 수 있다.