코드카타 13: minPathSum

문제

양수로 이루어진 m x n 그리드를 인자로 드립니다. 상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때, 가장 작은 합을 찾아서 return 해주세요.

한 지점에서 우측이나 아래로만 이동할 수 있습니다.

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

딱 보자마자 이 문제는 어려운 문제라는 생각이 들었다. 30분 동안 고민했는데 어떻게 구현해야 할지 로직 자체가 생각나지 않아 minPathSum 등의 단어로 구글링을 했고, leetcode의 문제라는 것을 알 수 있었다. 관련 답을 찾아보고 작성한 답은 다음과 같다.

const minPathSum = (grid) => {
  const m = grid[0].length;
  const n = grid.length;

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

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

문제대로 m과 n을 가로, 세로 길이로 설정하고, 배열을 순회한다. 문제의 조건 상 오른쪽과 아래로만 진행이 가능하므로, i, j가 0이라는 것은 진행 방향이 오른쪽으로만, 혹은 아래쪽으로만 진행되었다는 뜻이므로 해당 조건을 처리했다.

그 외엔 해당 요소까지 가는 최소 합을 계산했다. 위에서 올 때와 왼쪽에서 올 때를 비교해 더 작은 값을 해당 요소 값에 더해주면 해당 요소까지 갈 수 있는 최소 합이 된다.

이 과정을 반복하면 이 알고리즘의 목적지인 grid[n-1][m-1] 인덱스의 값이 해당 인덱스까지 가는 최소 합이 되므로, 해당 값을 반환하면 된다.