LeetCode - 최소 경로 합계

문제 설명

음수가 아닌 숫자로 채워진 m x n 격자가 주어지면,
왼쪽 상단에서 오른쪽 하단으로 경로를 따라 모든 숫자의 합을 최소화하는 경로를 찾습니다.

참고: 언제든지 아래 또는 오른쪽으로만 이동할 수 있습니다.

문제 진술 출처: https://leetcode.com/problems/minimum-path-sum

예 1:

Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

예 2:

Input: grid = [[1, 2, 3], [4, 5, 6]]
Output: 12

제약:

- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100

설명

무차별 대입 방식

무차별 대입 방식은 왼쪽 상단에서 오른쪽 하단까지 가능한 모든 경로를 생성하는 것입니다. 이 모든 경로의 합을 계산하고 최소값을 찾습니다. 이 솔루션은 작은 크기의 배열에서 작동하지만 큰 크기의 배열에서는 시간 초과됩니다.

최적의 하부구조

(m, n)에 도달하는 경로는 (m - 1, n) 또는 (m, n - 1)의 두 셀 중 하나를 통과해야 합니다. (m, n)에 도달하기 위한 최소 비용은 "2개의 셀과 그리드(m, n)의 최소값"으로 계산할 수 있습니다.

minimumCost(m, n) = min(minimumCost(m - 1, n), minimumCost(m, n - 1)) + grid(m, n)

int minCost(int grid[R][C], int m, int n)
{
    if (n < 0 || m < 0)
        return INT_MAX;
    else if (m == 0 && n == 0)
        return grid[m][n];
    else
        return grid[m][n] +
        min(
           minCost(grid, m - 1, n),
           minCost(grid, m, n - 1)
        );
}

동적 프로그래밍

위의 최적 하위 구조는 재귀적 접근 방식을 사용하여 해결됩니다. 그러나 자세히 살펴보면 위의 접근 방식은 동일한 하위 문제를 반복해서 계산합니다.

동적 프로그래밍 방식을 사용하여 동일한 하위 문제를 다시 계산하는 것을 피할 수 있습니다. 우리는 2D 배열을 생성하고 상향식 방식으로 문제를 해결합니다.

더 잘 이해하기 위해 알고리즘으로 넘어갑시다.

- set m = grid.size()
      n = grid[0].size()
      dp(m, vector<int>(n))

- loop for i = 0; i < m; i++
    loop for j = 0; j <n; j++

      if i == 0 && j == 0
        - set dp[i][j] = grid[i][j]
      else if i == 0
        - set dp[i][j] = dp[i][j - 1] + grid[i][j]
      else if j == 0
        - set dp[i][j] = dp[i - 1][j] + grid[i][j]
      else
        - set dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
- for end

- return dp[m - 1][n - 1]

이 접근법의 시간 복잡도는 O(N^2)이고 공간 복잡도는 O(M*N)입니다.

C++, Golang, Javascript에서 알고리즘을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if(i == 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if(j == 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else {
                    dp[i][j] = min(dp[i- 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
};

골랑 솔루션

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dp := make([][]int, m)

    for k := range dp {
        dp[k] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 {
                dp[i][j] = grid[i][j]
            } else if i == 0 {
                dp[i][j] = dp[i][j - 1] + grid[i][j]
            } else if j == 0 {
                dp[i][j] = dp[i - 1][j] + grid[i][j]
            } else {
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
            }
        }
    }

    return dp[m - 1][n - 1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

자바스크립트 솔루션

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

    for(let k = 0; k < dp.length; k++) {
        dp[k] = new Array(n);
    }

    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(i == 0 && j == 0) {
                dp[i][j] = grid[i][j];
            } else if(i == 0) {
                dp[i][j] = dp[i][j - 1] + grid[i][j];
            } else if(j == 0) {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
    }

    return dp[m - 1][n - 1];
};

예제 2의 알고리즘을 시험 실행해 보겠습니다.

Input: grid = [[1, 2, 3], [4, 5, 6]]

Step 1: m = grid.size()
          = 2
        n = grid[0].size()
          = 3

        dp(2, 3)

Step 2: loop for i = 0; i < m
          0 < 2
          true

          loop for j = 0; j < n
            0 < 3
            true

            if i == 0 && j == 0
               true

               dp[i][j] = grid[i][j]
                        = grid[0][0]
                        = 1

               dp = [[1, 0, 0], [0, 0, 0]]

            j++

            j = 1
            j < n
            1 < 3
            true

            if i == 0 && j == 0
               true
            else if i == 0
               true

               dp[i][j] = dp[i][j - 1] + grid[i][j]
                        = dp[0][1 - 1] + grid[0][1]
                        = dp[0][0] + grid[0][1]
                        = 1 + 2
                        = 3

               dp = [[1, 3, 0], [0, 0, 0]]

            j++
            j < n
            2 < 3
            true

            if i == 0 && j == 0
               true
            else if i == 0
               true

               dp[i][j] = dp[i][j - 1] + grid[i][j]
                        = dp[0][2 - 1] + grid[0][1]
                        = dp[0][1] + grid[0][2]
                        = 3 + 3
                        = 6

               dp = [[1, 3, 6], [0, 0, 0]]

            j++
            j < n
            3 < 3
            false

        i++
        i = 1

Step 3: loop for i < m
          1 < 2
          true

          loop for j = 0; j < n
            0 < 3
            true

            if i == 0 && j == 0
              false
            else if i == 0
              false
            else if j == 0
              true

              dp[i][j] = dp[i - 1][j] + grid[i][j]
                       = dp[1 - 1][0] + grid[1][0]
                       = dp[0][0] + grid[1][0]
                       = 1 + 4
                       = 5

              dp = [[1, 3, 6], [5, 0, 0]]

            j++
            j < n
            1 < 3
            true

            if i == 0 && j == 0
              false
            else if i == 0
              false
            else if j == 0
              false
            else

              dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
                       = min(dp[1][1 - 1], dp[1 - 1][1]) + grid[1][1]
                       = min(dp[1][0], dp[0][1]) + 5
                       = min(5, 3) + 5
                       = 3 + 5
                       = 8

              dp = [[1, 3, 6], [5, 8, 0]]

            j++
            j < n
            2 < 3
            true

            if i == 0 && j == 0
              false
            else if i == 0
              false
            else if j == 0
              false
            else

              dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
                       = min(dp[1][2 - 1], dp[1 - 1][2]) + grid[1][2]
                       = min(dp[1][1], dp[0][2]) + 6
                       = min(8, 6) + 6
                       = 6 + 6
                       = 12

              dp = [[1, 3, 6], [5, 8, 12]]


            j++
            j < n
            3 < 3
            false

        i++
        i = 2

Step 4: loop for i < m
          2 < 2
          false

Step 5: return dp[m - 1][n - 1]
               dp[2 - 1][3 - 1]
               dp[1][2]
               12

We return the answer as 12.