문제 설명

Minimum Path Sum - LeetCode

2D 격자(grid)에서 좌측 상단(0,0) → 우측 하단(m-1, n-1)으로 이동하는 최소 비용 경로를 찾는 문제입니다.

  • 오른쪽 또는 아래쪽으로만 이동 가능
  • 각 칸의 값은 해당 칸을 방문할 때 드는 비용
  • 최소 비용 경로의 합을 반환

✅ 제약 조건

  • 1 ≤ m, n ≤ 200 (격자 크기)
  • 0 ≤ grid[i][j] ≤ 100 (비용 값)
  • O(m × n) 이하의 시간 복잡도로 해결하는 것이 바람직

해설

1️⃣ DFS + 백트래킹 (O(2^(m+n))) → 비효율적

  • 모든 가능한 경로 탐색 → 시간 초과
  • O(2^(m+n)) → 너무 비효율적이므로 사용 불가

2️⃣ 동적 계획법 (DP, O(m × n)) [추천]

  • 최적 부분 구조를 가지므로 DP를 활용 가능
  • 점화식:
    • dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    • 즉, 위쪽 또는 왼쪽에서 오는 최소 비용 + 현재 위치 비용
  • 시간 복잡도: O(m × n)
  • 공간 복잡도: O(1) (grid를 직접 수정하여 사용 가능)

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def minPathSum(grid):
    m, n = len(grid), len(grid[0])

    # 첫 번째 행 초기화 (왼쪽에서 오는 값 누적)
    for j in range(1, n):
        grid[0][j] += grid[0][j - 1]

    # 첫 번째 열 초기화 (위쪽에서 오는 값 누적)
    for i in range(1, m):
        grid[i][0] += grid[i - 1][0]

    # DP 점화식 적용
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

    return grid[m - 1][n - 1]  # 우측 하단 값 반환

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

var minPathSum = function(grid) {
    let m = grid.length, n = grid[0].length;

    // 첫 번째 행 초기화
    for (let j = 1; j < n; j++) {
        grid[0][j] += grid[0][j - 1];
    }

    // 첫 번째 열 초기화
    for (let i = 1; i < m; i++) {
        grid[i][0] += grid[i - 1][0];
    }

    // DP 점화식 적용
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }

    return grid[m - 1][n - 1]; // 우측 하단 값 반환
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform