Skip to content

Leetcode - 931. Minimum Falling Path Sum

문제 개요

n x n 정사각 행렬 matrix가 주어진다. falling path 의 최소 합을 구해야 한다.

failling path는 아래와 같은 규칙을 가지고 있다.

  1. 첫 번째 열(row)에서 숫자를 선택한다.

  2. 첫 번째 열에서 갈 수 있는 곳은 왼쪽, 오른쪽 대각선 그리고 바로 밑이다.

  3. (row + 1, col - 1), (row + 1, col - 1), (row + 1, col - 1)

예로 들어 matrix가 아래와 같이 주어짐을 가정하자.

matrix: [[2, 1, 3] [6, 5 ,4] [7, 8 ,9]]

이때, [2,1,3] 중 숫자 1개를 선택하고, 다음은 [6,5,4], 마지막엔 [7,8,9] 중 선택하여 최소 합을 만족하는 수를 구하는 것이다. 위의 예제의 답은 13이다.

[1,5,7], [1,4,8] 의 합이 13이고, 이 경우가 최소합이기 때문이다.

해결 전략

이번 정답은 최소합만 구하면 되므로, 어떤 패턴이 최소합을 만족하는지는 신경쓰지 않는다. 그러나 어떻게 단계별로 접근해야 하는지 설계하는 것에 중점을 둔다.

matrix는 제일 첫 번째 열의 값을 먼저 선택한 후, 다음 열의 값을 선택한다. 이 때 최소값을 구하기 위해선 이전 값들 중 최소 값을 선택해야 한다. 그 다음 열도 마찬가지로 이전 열의 최소값을 선택하여 값을 구하는 전략을 세우면 아래와 같은 전략이 완성된다.

Image title

그림 1 - 해결 전략
class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        max_row = len(matrix)
        max_col = len(matrix[0])
        cache = [[0] * max_col for row in range(max_row)]

        # memoize first row
        for col in range(max_col):
            cache[0][col] = matrix[0][col]

        for row in range(1,max_row):
            for col in range(max_col):
                # center는 어느 열에서도 구할 수 있으므로, 확정시킨다.
                before_center = cache[row - 1][col]

                #left와 right는 값의 위치에 따라 다르므로 선택받지 않기 위해 제일 큰 값으로 지정한다. 
                before_left = before_right = float('inf')

                if col + 1 < max_col:
                    before_right = cache[row - 1][col + 1]

                if col - 1 >= 0:
                    before_left = cache[row - 1][col - 1]

                # 이전의 3개의 값 중 제일 작은 값과 더한다.
                before_minimum_value = min(before_left, before_center, before_right)
                cache[row][col] = before_minimum_value + matrix[row][col]

        # 마지막 열중 제일 작은 값을 선택한다.
        return min(cache[-1])

회고

명확한 부분

  1. 첫 번째 열부터 선택 하므로 첫번째 열의 값은 고정되어 있다.

  2. 다음 열에서 이전 열의 값을 비교하여 최소값인 수와 현재 가지고 있는 수를 더한다.

  3. 마지막 열의 최소값을 반환한다.

모호한 부분

graph로 알고 step에 따라 처리하려고 했다. 그러나 접근을 어떻게 디자인할지 감이 잡히지 않았다.

그러나 현재 알고 있는 graph의 접근 방식은 이전 값과 상호 작용하기 어려웠다. 현재 값과 next만 알 수 있기 때문이다.

dynamic programming은 graph와 차이가 있다. 이전 값의 경우의 수만큼 현재 값을 결정해야 하는 것이다.

이전에 푼 계단 문제도, 이전 경우의 수가 1 또는 2였다.

graph는 현재 값에서 다음 값을 찾기 최적화되어 있지만, 이전 경우의 수를 참고하여 현재 값을 결정하는 것에는 활용도가 떨어졌다.

이번 문제를 통해 dynamic programming 과 graph의 접근 방식의 차이점을 알게되었다.


#coding-interview

Comments