Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 행렬에서 가장 긴 증가 경로 찾기 (DFS + 메모이제이션)

문제 개요

하나의 행렬(matrix)이 주어졌을 때, 가장 긴 증가 경로(longest increasing path)의 길이를 구하는 문제입니다. 각 칸에서는 상하좌우 네 방향(왼쪽, 오른쪽, 위, 아래)으로만 이동할 수 있으며, 대각선 이동이나 행렬 경계 밖으로의 이동은 허용되지 않습니다.

예를 들어 다음과 같은 행렬이 입력으로 주어진다고 가정해 보겠습니다.

994
668
211

이 경우 출력값은 4입니다. 초록색으로 표시된 칸들을 따라 [1, 2, 6, 9] 경로가 만들어지는데, 왼쪽 아래의 1에서 시작해 2 → 6 → 9 순서로 값을 증가시키며 위쪽으로 이동하는 경로의 길이가 4이기 때문입니다.

풀이 접근 방식

이 문제는 DFS(깊이 우선 탐색)와 메모이제이션(memoization)을 결합한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 각 칸에서 시작하는 최장 증가 경로의 길이를 DP 테이블에 저장해 두면, 같은 칸을 반복해서 탐색하는 낭비를 없앨 수 있습니다.

알고리즘 단계

  • solve(i, j, matrix) 함수를 정의합니다.

  • dp[i][j] 값이 0이 아니라면 이미 계산된 결과이므로 그대로 반환합니다.

  • dp[i][j] := 1로 초기화합니다(자기 자신을 경로의 시작점으로 포함).

  • temp := 0으로 설정합니다.

  • r을 i-1부터 i+1까지 반복합니다.

    • c를 j-1부터 j+1까지 반복합니다.

      • (r, c)가 현재 위치와 같거나 대각선 방향이라면 다음 반복으로 건너뜁니다.

      • (r, c)가 행렬 범위 안에 있고 matrix[r][c] > matrix[i][j]를 만족한다면, temp := max(temp, solve(r, c, matrix))로 갱신합니다.

  • dp[i][j] := dp[i][j] + temp로 갱신합니다.

  • dp[i][j]를 반환합니다.

메인 함수 처리 과정

  • 행렬이 비어 있다면 0을 반환합니다.

  • 입력 행렬과 같은 크기의 DP 테이블을 0으로 채워 생성합니다.

  • ans := 0으로 초기화합니다.

  • 모든 칸을 순회하면서 dp[i][j]가 0인 경우 solve(i, j, matrix)를 호출하고, ans를 각 칸의 DP 값과 비교해 최댓값으로 갱신합니다.

  • ans를 반환합니다.

구현 예제

다음 구현을 통해 더 잘 이해해 보겠습니다.

class Solution(object):
   def solve(self, i, j, matrix):
      if self.dp[i][j]:
         return self.dp[i][j]
      self.dp[i][j] = 1
      temp = 0
      for r in range(i-1, i+2):
         for c in range(j-1, j+2):
            if (r == i and c == j) or (abs(r-i) == 1 and abs(c-j) == 1):
               continue
            if c >= 0 and r >= 0 and r < len(matrix) and c < len(matrix[0]) and matrix[r][c] > matrix[i][j]:
               temp = max(temp, self.solve(r, c, matrix))
      self.dp[i][j] += temp
      return self.dp[i][j]

   def longestIncreasingPath(self, matrix):
      if not matrix:
         return 0
      self.dp = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
      self.ans = 0
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if self.dp[i][j] == 0:
               self.solve(i, j, matrix)
            self.ans = max(self.ans, self.dp[i][j])
      return self.ans

ob = Solution()
print(ob.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))

입력

[[9,9,4],[6,6,8],[2,1,1]]

출력

4

복잡도 분석

시간 복잡도: O(m × n) — 메모이제이션 덕분에 각 칸은 한 번만 완전히 계산되며, 각 칸에서 상수 개의 인접 칸만 확인합니다. 여기서 m과 n은 각각 행렬의 행과 열의 개수입니다.

공간 복잡도: O(m × n) — DP 테이블과 재귀 호출 스택에 추가 공간이 필요합니다.