파이썬(Python)으로 풀어보는 최소 경로 합계(Minimum Path Sum) 알고리즘

문제 소개

m x n 크기의 행렬이 음수가 아닌 정수들로 채워져 있다고 가정해 보겠습니다. 이때 왼쪽 상단 모서리에서 오른쪽 하단 모서리까지 이동하는 경로 중, 경로 위에 있는 모든 숫자의 합을 최소화하는 경로를 찾아야 합니다. 단, 이동은 언제나 아래 또는 오른쪽 방향으로만 가능하다는 제약 조건이 있습니다.

예를 들어 다음과 같은 행렬이 주어졌다고 가정해 봅시다.

위 행렬의 경우 출력값은 7이 됩니다. 최적 경로는 1 → 3 → 1 → 1 → 1 순서로 진행되며, 이 경로가 가능한 모든 경로 중 가장 작은 합을 만듭니다.

알고리즘 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 칸에 도달할 수 있는 최소 비용을 행렬 자체에 누적하여 저장하는 것입니다. 오른쪽 끝 열과 아래쪽 끝 행부터 역순으로 처리한 뒤, 나머지 칸들은 오른쪽 칸과 아래쪽 칸 중 더 작은 값을 더해 나갑니다.

단계별 과정은 다음과 같습니다.

• a := 행의 개수, b := 열의 개수로 설정
• 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 := 행 개수 − 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):
      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])
ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))

입력

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

출력

7

정리

이 알고리즘은 별도의 추가 배열 없이 입력 행렬 자체를 활용하기 때문에 공간 복잡도가 O(1)이며(입력 수정이 허용되는 경우), 모든 칸을 한 번씩만 방문하므로 시간 복잡도는 O(m x n)입니다. 격자(grid) 기반 경로 탐색 문제에서 자주 등장하는 대표적인 동적 계획법 패턴이므로, 코딩 테스트 준비 시 꼭 익혀두면 유용합니다.