C++로 구현하는 최소 경로 합계(Minimum Path Sum) 알고리즘

음이 아닌 정수로 채워진 m × n 크기의 행렬이 있다고 가정해 봅시다. 이때 좌측 상단 모서리에서 우측 하단 모서리까지 이동하는 경로 중, 경로에 포함된 숫자들의 합이 최소가 되는 경로를 찾는 것이 목표입니다.

여기서 중요한 제약 조건은 한 번에 이동할 수 있는 방향이 아래쪽 또는 오른쪽으로만 가능하다는 점입니다.

예를 들어 다음과 같은 행렬이 주어졌다고 해보겠습니다.

1	3	1
1	5	1
4	2	1

이 경우 출력값은 7입니다. 실제 최소 경로는 1 → 3 → 1 → 1 → 1이며, 이 경로를 따라 이동했을 때 숫자의 합이 가장 작아지기 때문입니다.

알고리즘 접근 방식

이 문제는 대표적인 동적 계획법(Dynamic Programming) 유형으로, 각 칸에서 도달 가능한 최소 누적 합을 행렬 자체에 저장하며 뒤에서부터(우하단에서 좌상단 방향으로) 계산해 나가는 방식으로 해결할 수 있습니다. 추가 배열 없이 입력 행렬을 그대로 활용하므로 메모리 사용량도 절약됩니다.

알고리즘 단계

a := 행(row)의 개수, b := 열(column)의 개수로 설정합니다.
i := a − 1, j := b − 1로 초기화합니다.
j ≥ 0인 동안 반복합니다.
- matrix[a, j] := matrix[a, j] + matrix[a, j + 1] — 마지막 행의 각 칸에 오른쪽 값을 더해 누적합니다.
- j를 1씩 감소시킵니다.
i ≥ 0인 동안 반복합니다.
- matrix[i, b] := matrix[i, b] + matrix[i + 1, b] — 마지막 열의 각 칸에 아래쪽 값을 더해 누적합니다.
- i를 1씩 감소시킵니다.
j := b − 1, i := row − 1로 다시 초기화합니다.
i ≥ 0인 동안 반복합니다.
- j ≥ 0인 동안 반복합니다.
  - matrix[i, j] := matrix[i, j] + min(matrix[i, j + 1], matrix[i + 1, j]) — 현재 칸에 '오른쪽 값'과 '아래쪽 값' 중 작은 것을 더합니다.
  - j를 1씩 감소시킵니다.
- j := b − 1로 초기화합니다.
- i를 1 감소시킵니다.
모든 과정이 끝나면 matrix[0, 0]에 최소 경로 합이 저장되어 있으므로 이를 반환합니다.

예제 코드

아래 구현 예제를 통해 동작 원리를 더 잘 이해해 보겠습니다.

class Solution(object):
   def minPathSum(self, grid):
      """
      :type grid: List[List[int]]
      :rtype: int
      """
      row = len(grid)-1
      column = len(grid[0])-1
      i=row-1
      j=column-1
      while j>=0:
         grid[row][j]+=grid[row][j+1]
         j-=1
      while i>=0:
         grid[i][column]+=grid[i+1][column]
         i-=1
      j=column-1
      i = row-1
      while i>=0:
         while j>=0:
         grid[i][j] += min(grid[i][j+1],grid[i+1][j])
         j-=1
      j=column-1
      i-=1
   return(grid[0][0])

입력

[[1,3,1],[1,5,1],[4,2,1]]

출력

정리

이 알고리즘은 행렬의 모든 칸을 한 번씩만 방문하므로 시간 복잡도는 O(m × n)이며, 별도의 DP 테이블을 만들지 않고 입력 행렬을 재활용하기 때문에 공간 복잡도도 O(1)(입력 행렬 제외)로 매우 효율적입니다. 격자(grid) 기반 경로 탐색 문제에서 널리 활용되는 패턴이므로, 코딩 테스트 준비 시 꼭 익혀두면 좋습니다.