LeetCode: 64번 (Minimum Path Sum) [JAVA]

문제 링크

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

Minimum Path Sum - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 이차원 배열 grid를 활용, 우선 0번째 행의 열들을 증가하는 순서대로 누적값을 저장, 0번째 열의 행들을 증가하는 순서대로 누적값을 저장
2. 그 다음 이외의 요소들에 대해선 현 위치의 값에 왼쪽 값과 위의 값 중 더 작은 값을 더하여 저장
3. 최종 위치 값인 배열의 오른쪽 아래 요소 값을 반환

 문제의 내용은 약간 상이하지만, 앞서 풀었던 62. Unique Paths 문제와 풀이가 매우 비슷한 문제이다. 주어진 이차원 배열 grid에서 왼쪽 위부터 오른쪽 아래로 가는 최단거리 경로 중 가장 적은 숫자 합을 반환하는 문제이다. 결국 모든 경로의 탐색을 진행해야 하지만 최단 경로기 때문에, 현 위치에 올 수 있는 경로는 현 위치에서 왼쪽으로 오는 경로나 위에서 내려오는 경로뿐이다. 그렇기에 경로의 가장 적은 합을 계산할 때도 해당 부분만 비교하면 된다.
 우선 주어진 이차원 배열 grid에서 0번째 행의 열들을 증가하는 순서대로 누적값을 저장, 0번째 열의 행들을 증가하는 순서대로 누적값을 저장한다. 그 외의 요소에 대해선, 왼쪽 위부터 순차대로 이중 for문을 통해 grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]) 형태로 값을 계산하여 저장하면 된다. 이후 목적지인 이차원 배열의 오른쪽 아래 위치의 값을 반환하면 된다.

 

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        for (int i = 1; i < m; i++) {//행따라 숫자값 누적
            grid[i][0] += grid[i - 1][0];
        }

        for (int i = 1; i < n; i++) {//열따라 숫자값 누적
            grid[0][i] += grid[0][i - 1];
        }

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {//현 위치의 값에 직전 왼쪽 값과 직전 위쪽 값중 최소를 더함 
                grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);
            }
        }

        return grid[m - 1][n - 1];//최종 위치 값 반환
    }
}

결과