위코드 코드카타를 정리한 내용입니다.

문제

양수로 이루어진 m x n 그리드를 인자로 받고 상단 왼쪽에서 시작해 하단 오른쪽까지 가는 길의 요소를 다 더했을 때 가장 합이 작은 값을 찾아서 리턴하세요. 한 지점에서 우측이나 아래로만 이동할 수 있습니다.

// input, 배열안 배열요소로 나열 된 상태
[
	[1, 3, 1],
	[1, 5, 1],
	[4, 2, 1]
]

// output
7

풀이

grid[0][0] 으로 특정 값을 선택한다면 그리드 구조는 아래와 같습니다.
00 / 01 / 02
10 / 11 / 12
20 / 21 / 22

이 기준으로 첫번째 세로줄만 합을 더하면 아래와 같습니다. 경로가 하나이므로 최소값을 비교할 필요가 없고 이동하면서 이전 값을 더해둡니다. 10 에 00의 값을 더해 넣어주고 20에 10을 값을 더해서 넣어줍니다.

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]
}

이제 가운데 들어가는 값을 더해줍니다. 11, 12, 21, 22 순으로 값을 구하는데, 11의 경우 01 과 10 중 최소값을 더해주고 12의 경우 02 와 11 의 값 중 최소값을 더해줍니다. 해당값으로 넘어올 수 있는 경우는 이렇게 두가지 이므로 개중 작은 값을 더해서 최종값을 남깁니다. 최종적으로 22 라는 끝 점까지 최소값으로 합해진 값이 들어옵니다.

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]);
  }
}

최종 결과값의 위치는 각 길이의 -1 을 한 인덱스 넘버입니다.

return grid[grid.length - 1][grid[0].length - 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];
};