[leetCode/JS] 931. Minimum Falling Path Sum

난이도 [ 🤔 ] Medium

문제 설명

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

n x n 정수 배열이 주어진다.
이 배열의 "falling path"중 가장 작은 합계의 숫자를 반환하면 된다.
falling path는 (row, col) 에서 (row+1, col-1), (row+1, col), (row+1, col+1)의 3가지 경로를 가질 수 있다. 

 

입출력 예

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

 

 

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

 

 

Constraints

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

 

---

 

내 솔루션

• falling path 라는 개념을 처음에 안읽고 지나가서 잠깐 정신 놓고 딴거 만들고 있었다. 😂
• 경로 자체를 구하는 것이 아니고 합계를 구한다는 점이 중요.
• 설명에 있는 낙하 개념으로 접근함.

2	1	3	➔	2	1	3	➔	2	1	3
6	5	4		7	6	5		7	6	5
7	8	9		7	8	9		13	13	14

• row = 1 부터 시작해서 [row-1]에 있는 [col-1], [col], [col+1] 중 가장 작은 숫자와 합친다.
• [row][-1] 이나 [row][col.length < n]가 되어 undefined 일 수 도있으니 체크한다.
• matrix의 마지막 row중 가장 작은 숫자를 return하면 답이 된다.

var minFallingPathSum = function(matrix) {
  const check = (n) =>  n !== undefined ? n : Infinity;
  for(let row = 1; row < matrix.length; row++) {
    for(let col = 0; col < matrix[0].length; col++) {
      matrix[row][col] = matrix[row][col] + 
      	Math.min(
          check(matrix[row-1][col-1]),
          check(matrix[row-1][col]),
          check(matrix[row-1][col+1])
        );
    }
  }
  return Math.min(...matrix[matrix.length-1]);
};

처음에 짠 보기 좋은 코드. 속도 103ms, 메모리 42.7MB.

 

 

 

var minFallingPathSum = function(matrix) {
  for(let row = 1; row < matrix.length; row++) {
    for(let col = 0; col < matrix[0].length; col++) {
      matrix[row][col] = matrix[row][col] + Math.min(
        matrix[row-1][col-1] !== undefined ? matrix[row-1][col-1] : Infinity,
        matrix[row-1][col] !== undefined ? matrix[row-1][col] : Infinity,
        matrix[row-1][col+1] !== undefined ? matrix[row-1][col+1] : Infinity,
      );
    }
  }
  return Math.min(...matrix[matrix.length-1]);
};

보기엔 화남. 속도 89ms, 메모리 43.5 MB

 

감상평

• 처음엔 DFS를 이용하려다가 복잡해져서 정신 놔버림.ㅋㅋ
• 그후엔 row를 역순으로 올라가는 코드로 짰다가. 내려가도 된다는 생각이 들어서 다시 row++로 짬.
• 분명 미디엄이였는데..  많이 풀어봐야 쉬운 문제들이 많다.