LeetCode 329: 행렬에서 가장 긴 증가 경로 — 단계별 시각적 추적

Source: Dev.to

문제 설명

인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로 이동하면서 값이 엄격히 증가하는 셀만을 따라갈 수 있는 행렬에서 가장 긴 증가 경로의 길이를 찾으세요.

접근 방법

해결 방법은 깊이 우선 탐색(DFS)과 메모이제이션을 사용합니다:

1. 각 셀에서 DFS를 수행해 가능한 모든 증가 경로를 탐색합니다.
2. 각 셀에서 시작하는 가장 긴 경로의 길이를 DP(메모이제이션) 테이블에 저장해 중복 계산을 방지합니다.
3. 모든 시작 위치에 대해 DP 테이블에서 찾은 최대값이 정답이 됩니다.

복잡도 분석

• 시간: O(m × n) – 메모이제이션 덕분에 각 셀은 한 번만 처리됩니다.
• 공간: O(m × n) – DP 테이블과 재귀 호출 스택을 위해 필요합니다.

참고 구현 (Python)

from typing import List

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

        # Directions: up, down, left, right
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        m, n = len(matrix), len(matrix[0])
        dp = [[-1] * n for _ in range(m)]  # memoization table

        def dfs(i: int, j: int) -> int:
            # Return cached result if already computed
            if dp[i][j] != -1:
                return dp[i][j]

            # At least the cell itself
            dp[i][j] = 1

            # Explore neighbors
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    dp[i][j] = max(dp[i][j], 1 + dfs(x, y))

            return dp[i][j]

        max_path = 0
        for i in range(m):
            for j in range(n):
                max_path = max(max_path, dfs(i, j))

        return max_path

인터랙티브 시각화

직접 해보세요: Open TraceLit and step through every line – LeetCode 연습을 위한 시각적 알고리즘 트레이서 TraceLit으로 제작되었습니다.