[Leet code - 64] Minimum Path Sum ✅

Minimum Path Sum - LeetCode

문제

Input : 2차원 배열 grid (Vector<Vector>)

output : 좌측상단에서 우측하단까지의 여러 경로 중, 각 경로 상 등장하는 숫자의 합 중에 최소 값을 반환

※우측과 하단으로만 움직일 수 있음

 

 

시간 복잡도

※1초에 1억번을 대략적인 기준으로 삼는다.

$1 <= y, x <= 200$

 

최소 연산단위는 2차원배열의 원소 하나이므로 n은 전체 원소의 수로 생각했다.

$O(n) = y * x = 200 * 200 = 40'000$

 

• $n^2 = 40'000 \times 40'000 = 1'600'000'000$❌
• $n \log n = 40'000 \times 15 \approx 600'000$✅
  $n \log n$이하의 복잡도를 목표로 풀이한다.

 

해결 계획

처음에는 어차피 결국 모든 경로를 확인해야 하는 거 아닌가 했다.

그래서 DFS는 불가능하니 BFS를 사용하려했지만, 최근에 푼 문제가 생각나서 n으로 풀 수 있겠다 생각했다.

 

이런걸 n으로 풀려면 메모제이션은 당연히 동반되어야한다.

그래서 어떤 걸 저장하냐면, dp[y][x] =  grid[0][0]에서 grid[y][x] 까지의 경로 중 최소 값 이다.

 

경로의 이동은 우측 아니면 하단 밖에 없기 때문에, [y][x]로 들어오는 경로는 [y-1][x]과 [y][x-1]밖에 없다.

그렇기 때문에 두 좌표중 작은 값을 가져와서 더하면 그게 현재 좌표에서 얻을 수 있는 최소 값이다.

 

더하여, 반환 값이 int로 충분한지 검토했다.

원소의 최대값은 200이므로 결과로 나올 수 있는 최대값은 $200 \times 400 = 80'000$로 충분했다.

 

아래는 구현 전 작성했던 수도 코드다.

 

수도 코드를 작성하면서 변경한 점이 있는데,

따로 DP 테이블을 생성하지 않고, 원본 배열에 메모제이션을 적용하여 추가 공간 없이 진행했다.

값을 누적해나가면서 기존의 값들을 가지고 있어야 할 필요는 없었기 때문에 괜찮다고 생각했다.

gridY = grid height
gridX = grid width

// 초기값 설정 
맨 윗줄과 맨 왼쪽줄 각 누적해서 더해가면 됨

// 각 셀 계산
for (y from 1 to gridY -1)
	for(x from 1 to gridX - 1)
	{
		grid[y][x] += std::min(grid[y-1][x], grid[y][x-1]);
	}

return grid[gridY - 1][gridX - 1];

 

간단한 시뮬레이션을 돌리고 잘 동작하는 것 같아 구현에 들어갔다.

• Grid
  1 3 1
  2 2 1
  1 4 1
  
  
• 초기 값 설정 후
  1 4 5
  3 2 1
  4 4 1
  
  
• Loop 후
  1 4 5
  3 5 6
  4 6 7
  
  
• Result : 7 ✅

 

구현

int minPathSum(vector<vector<int>>& grid) {

        int gridY = grid.size();
        int gridX = grid[0].size();

        // 초기값 설정
        for (int y = 1; y < gridY; ++y)
            grid[y][0] += grid[y - 1][0];

        for (int x = 1; x < gridX; ++x)
            grid[0][x] += grid[0][x - 1];

        // Loop
        for (int y = 1 ; y < gridY ; ++y)
        {
            for(int x = 1; x < gridX; ++x)
            {
                grid[y][x] += std::min(grid[y-1][x], grid[y][x-1]);
            }
        }
        
        // Result
        return grid[gridY - 1][gridX - 1];
    }