문제 소개
2차원 행렬이 주어졌을 때, 그 안에서 찾을 수 있는 가장 긴 엄격하게 증가하는 경로(strictly increasing path)의 길이를 구하는 것이 목표입니다. 경로를 따라 이동할 때는 위, 아래, 왼쪽, 오른쪽 네 방향으로만 움직일 수 있으며, 대각선 이동은 허용되지 않습니다.
예를 들어 다음과 같은 행렬이 입력으로 주어진다고 가정해 보겠습니다.
| 2 | 4 | 6 |
| 1 | 5 | 7 |
| 3 | 3 | 9 |
이 경우 정답은 6입니다. 가장 긴 경로가 [1, 2, 4, 6, 7, 9]이기 때문입니다.
풀이 접근 방식
이 문제는 깊이 우선 탐색(DFS)을 활용한 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 셀을 시작점으로 삼아, 인접한 네 방향 중 현재 값보다 큰 값을 가진 셀로만 이동하면서 재귀적으로 경로 길이를 계산하는 것입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
n := 행렬의 행 개수, m := 행렬의 열 개수
moves := 상하좌우 이동을 나타내는 좌표 쌍 리스트 [[1, 0], [-1, 0], [0, 1], [0, -1]]
dp(y, x) 함수 정의:
만약 (y, x)가 행렬 범위를 벗어나면
0을 반환
currVal := matrix[y][x]
res := 0
moves의 각 방향 d에 대해 반복:
(dy, dx) := d
(newY, newX) := (y + dy, x + dx)
만약 (newY, newX)가 행렬 범위 안에 있고 matrix[newY][newX] > currVal이면
res := max(res, dp(newY, newX))
res + 1 반환
메인 로직:
result := 0
i를 0부터 n-1까지 반복:
j를 0부터 m-1까지 반복:
result := max(result, dp(i, j))
result 반환
Python 예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, matrix):
n, m = len(matrix), len(matrix[0])
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def dp(y, x):
if y < 0 or y >= n or x < 0 or x >= m:
return 0
currVal = matrix[y][x]
res = 0
for dy, dx in moves:
newY, newX = y + dy, x + dx
if 0 <= newY < n and 0 <= newX < m and matrix[newY][newX] > currVal:
res = max(res, dp(newY, newX))
return res + 1
result = 0
for i in range(n):
for j in range(m):
result = max(result, dp(i, j))
return result
ob = Solution()
matrix = [
[2, 4, 6],
[1, 5, 7],
[3, 3, 9]
]
print(ob.solve(matrix))
입력
[[2, 4, 6], [1, 5, 7], [3, 3, 9]]
출력
6
성능 개선 팁
위 구현은 같은 셀을 여러 번 다시 계산하는 중복 연산이 발생할 수 있습니다. @lru_cache 데코레이터나 딕셔너리를 활용한 메모이제이션을 적용하면, 각 셀에서 시작하는 최장 경로 길이를 한 번만 계산하므로 전체 시간 복잡도를 셀 개수에 비례하는 O(n×m) 수준으로 크게 줄일 수 있습니다.