[LeetCode] 931. Minimum Falling Path Sum

행렬을 더하면서 내려갔을때 나오는 최소값을 구하는 문제로 x축으로는 -1, 0, 1만큼 이동할 수 있다.

끝 값이 어떻게 바뀔지 모르기 때문에 전부 확인해야 된다고 생각해서 방향 배열을 만들고 queue에다 계속 값을 더해가면서 전부 탐색을 했는데 역시 시간 초과가 발생했다.

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        Queue<Point> queue = new LinkedList<>();
        int min = Integer.MAX_VALUE;
        int n = matrix.length;
        int[] dx = new int[]{-1, 0, 1};

        for (int i = 0; i < n; i++) {
            queue.offer(new Point(0, i, matrix[0][i]));
        }

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int j = 0; j < 3; j++) {
                int mx = point.x + dx[j];
                int my = point.y + 1;
                if (my >= n) {
                    min = Math.min(min, point.sum);
                    continue;
                }
                if (mx < 0 || mx >= n) {
                    continue;
                }
                queue.offer(new Point(my, mx, point.sum + matrix[my][mx]));
            }
        }
        return min;
    }

    public static class Point {
        int y;
        int x;
        int sum;

        public Point(int y, int x, int sum) {
            this.y = y;
            this.x = x;
            this.sum = sum;
        }
    }
}

 

다른 풀이 코드를 확인해보니 이전 행에서 될 수 있는 최소값을 비교해가면서 구하는 식으로 깔끔하게 구현을 했다. 해당 자리에 올 수 있는 방법은 이전 행의 x축 [-1, 0, 1] 3가지 경우이기 때문에 3가지만 비교하면 된다. 인덱스 바운스를 Math.max(0, x - 1), Math.min(end, x + 1)로 처리할 생각은 못 해봤는데 하나 배웠다.

 

public int minFallingPathSum(int[][] matrix) {
    // n x n matrix
    int n = matrix.length;

    for (int y = 1; y < n; y++) {
        for (int x = 0; x < n; x++) {
            int middle = matrix[y - 1][x];
            int sideMin = Math.min(
                matrix[y - 1][Math.max(0, x - 1)], 
                matrix[y - 1][Math.min(n - 1, x + 1)]
            );

            matrix[y][x] += Math.min(middle, sideMin);
        }
    }

    return Arrays.stream(matrix[n - 1]).min().getAsInt();
}

 

Minimum Falling Path Sum - LeetCode