Minimum Path Sum(leetcode, 64)

문제 설명

mxn 배열이 주어졌을 때, 오른쪽 혹은 아랫쪽으로 움직여서 (0,0)에서 (m-1, n-1)까지 가는 최솟값을 찾는 문제다.

문제 풀이

첫 번째 접근

당연히 너비 우선탐색일 거라고 생각했다. 그래서 원래 풀던 대로 풀었더니 시간 초과가 났다. 엉..?

두 번째 접근

아, 오른쪽하고 아래만 갈 수 있으니까 2차원 반복문으로 풀 수 있겠구나 싶었다. 그래서 풀었는데, 문제는 얘가 오른쪽으로 전부 가고 내려가기 때문에 오른쪽과 아랫쪽 값을 비교하지 못한다는 것이었다.

그래서 내려가기만 하는 경우(j가 0일때)와 오른쪽으로 가기만 하는 경우(i가 0일때)를 따져줘도 풀 수 없었다.

아니, 도대체 pair 클래스를 만들어서 큐에 넣어주는 너비 우선 탐색이 아니면 뭔데?

세 번째 접근(다른 사람의 풀이)

도저히 너비 우선 탐색밖에 생각이 안 나서 다름 사람의 풀이를 봤다. 나의 두 번째 비슷하지만 훨씬 간단한 풀이었다.

1. 오로지 내려가는 방향만 있는 (i, 0)에는 내려가는 누적 값을 미리 넣어준다.

2. 오른쪽으로 움직이는 방향만 있는 (0, j)에는 오른쪽으로 가는 누적 값을 미리 넣어준다.

3. i와 j를 1부터(1과 2에 두 값이 0이 되는 합은 미리 구했다) 위에서 아래로 오는 값 (i-1, j)과 왼쪽에서 오른쪽으로 오는 값(i, j-1)의 최소 값을 해당 위치에다가 더하면 된다.

엄청 간단하다. 그냥 문제를 처음 봤을 때 너비 우선 탐색이라고 결정해버려서 문제를 제대로 보지 못한 거 같다.

코드

Java

import java.util.*;
import java.io.*;


class Solution {

    public int minPathSum(int[][] grid) {
        int[][] count = new int[grid.length][grid[0].length];

        for(int i=1; i<count.length; i++){
            grid[i][0] += grid[i-1][0];
        }

        for(int j=1; j<count[0].length; j++){
            grid[0][j] += grid[0][j-1];
        }


        for(int i=1; i<grid.length; i++){
            for(int j=1; j<grid[0].length; j++){
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }

        }


        return grid[grid.length-1][grid[0].length-1];
    }

}

링크

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