[LeetCode] Minimum Path Sum (javascript)

좌상단에서 출발하여 우하단까지 오른쪽, 아래로만 움직여 도착해야 한다.

가는 경로의 숫자를 모두 더했을때, 가장 작은 숫자를 구하는 문제다.

 

최단경로 경우의 수 문제와 유사하게 풀 수 있다.

 

처음엔 모든 경로를 처음부터 더해가면서 최솟값을 구해보려고 했으나..

(첫번째 경로 결과 : 10, 두번째 경로 결과 : 8 ...)

Time Limit에 걸렸다.

이미 구해놓은 결과값보다 큰 경우 패스하도록 해도 마찬가지...

틀린 풀이

// 잘못된 접근방식(Time Limit)
var minPathSum = function (grid) {
    let result = Infinity;
    const ml = grid.length - 1;
    const nl = grid[0].length -1;
    console.log(ml, nl)
    
    const moveNSum = (m, n, sum) => {
        if (result <= sum) return;
        if (m == ml && n == nl) {
            console.log('도착', 'result', result, 'sum',sum);
            result = sum;
        }
        // go right
        if (Number.isInteger(grid[m][n + 1])) {
            moveNSum(m, n + 1, sum + grid[m][n + 1]);
        }

        // go down
        if (grid[m + 1]) {
            moveNSum(m + 1, n, sum + grid[m + 1][n]);
        }
        return result;
    };
    moveNSum(0, 0, grid[0][0]);
    return result;
};

 

결국 다른 방식을 생각하게 되었는데, 각 위치마다의 최솟값을 저장해나가며 마지막 값을 리턴하도록 개선했다.

 

grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
];

newGrid = [
    [1     , 4(L+3), 5(L+1)],
    [2(U+1), 7(L+5), 6(U+1)],
    [6(U+4), 8(L+2), 7(U+1)],
];

newGrid를 보면, 첫 가로줄은 무조건 좌측+요소값, 첫 세로줄은 무조건 윗쪽+요소값이다.

그 후부터는 좌측과 상단 중 작은 값 + 요소값이다.

 

결국 모두 구한 후 가장 우하단의 값이 최솟값이 된다.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
    // n = 가로, m = 세로
    const n = grid[0].length;
    const m = grid.length;

    // left, down으로 움직이며 m, n까지 가는 최소값을 저장해나가면서 계산한다...
    const newGrid = grid;
    // min(top + current, left + current)

    // i = 가로, j = 세로
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (i == 0 && j == 0) continue;
            if (i == 0) {
                newGrid[j][i] = newGrid[j - 1][i] + newGrid[j][i];
                continue;
            }
            if (j == 0) {
                newGrid[j][i] = newGrid[j][i - 1] + newGrid[j][i];
                continue;
            }

            newGrid[j][i] = Math.min(
                newGrid[j][i - 1] + newGrid[j][i],
                newGrid[j - 1][i] + newGrid[j][i]
            );
        }
    }
    console.log(newGrid);
    return newGrid[m - 1][n - 1];
};

 

https://leetcode.com/problems/minimum-path-sum/