📋 양수로 이루어진 Grid에서 합이 가장 낮은 길 찾기

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

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

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

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

---

📌 1. 모범 답안

1시간동안 모든 경우의 수를 찾은 후 가장 작은 값을 구해야할지,
아니면 최적의 루트를 비교하며 찾아야할지를 고민하다가 결국 모든 경우의 수를 찾아 가장 작은 값을 구하는 방법으로 구현해보려했지만 실패했고 결국 모범 답안을 찾게되었다.

const minPathSum = grid => {
  for (let i = 1; i < grid.length; i++) {
    grid[i][0] += grid[i - 1][0];
  }

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

  for (let i = 1; i < grid.length; i++) {
    for (let 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];
  // 우측 맨 밑 리턴
};

처음봤을 때, 나는 이해하기 조금 어려워 console에 찍어가며 이해했다.
내가 이해한 부분을 바탕으로 코드를 설명해보겠다.

[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

우선 이 Grid를 Input으로 넣었다고 가정하겠다.

첫 번째 for문과 두 번째 for문을 통해 각 배열의 0번 인덱스 값(y축)과 0번 인덱스 배열(x축)의 값을 누적시킨값으로 바꿔준다.

[
  [1, 4, 5], 
  [2, 5, 1], 
  [6, 2, 1]
]

이제 2개의 선택지가 있는 양수인
1번 인덱스 배열의 1번, 2번, 2번인덱스의 1번, 2번에 세 번째 for문을 통해 2개의 선택지중 더 낮은값을 추가해준다.

  [ 1, 4, 5 ],
  [ 2, 7, 6 ],
  [ 6, 8, 7 ]

그렇다면 Grid는 이런 형태로 나오게 된다.
이제 마지막 인덱스 배열의 마지막 인덱스값을 return하면 끝이다.