[LeetCode] 1594. Maximum Non Negative Product in a Matrix

문제 출처: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/

Maximum Non Negative Product in a Matrix - LeetCode

문제

rows x cols 행렬 grid가 주어진다. 초기에 당신은 왼쪽 상단 모서리인 (0, 0)에서 시작하여 각 단계마다 오른쪽 또는 아래로 움직일 수 있다.

 

(0, 0)에서 시작하여 오른쪽 하단 모서리 (rows - 1. cols - 1)까지 이어지는 모든 경로 중에서 음이 아닌 최대 경로의 곱을 찾아라. 경로의 곱은 방문한 칸의 모든 정수들의 곱이다.

 

음이 아닌 최대 곱을 10^9 + 7로 나눈 나머지를 반환하라. 만약 음의 값이라면 -1을 반환하라.

 

나머지 연산은 최종 곱 계산 이후에 적용하라.

예제

Input: grid = [[-1,-2,-3],
               [-2,-3,-3],
               [-3,-3,-2]]
Output: -1

Explanation: It's not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.

Input: grid = [[ 1, 4,4,0],
               [-2, 0,0,1],
               [ 1,-1,1,1]]
Output: 2

Explanation: Maximum non-negative product is in bold (1 * -2 * 1 * -1 * 1 * 1 = 2).

풀이

문제를 보고 떠올린 첫 방법은 BFS입니다.

 

전체적인 방식은 다음과 같습니다.

 

(0,0)에서 시작하여 우측 또는 아래로 움직이며, 도착한 셀에 대한 Max, Min 값을 업데이트합니다. 모든 과정이 끝난 이후, 마지막 셀에 저장된 Max값을 통해 -1을 반환할지 해당 값을 반환할지 결정합니다.

 

여기서 Max와 Min값을 사용하는 이유는, 셀 값에 음수가 저장될 수 있기 때문입니다. 음수 값이 곱해짐에 의해 부호가 바뀌기 때문에 이를 고려하기 위해서 Max값만 저장하는 것이 아닌 Min값도 같이 저장하는 것입니다.

 

이를 코드로 작성하면 다음과 같습니다.

function maxProductPath (grid) {
    // memo: rows x cols의 2차원 배열
    // memo[i][j] = { max: maxVal, min: minVal }

    const queue = [[0, 0, -1, -1]]
    while (queue.length) {
        let [x, y, preX, preY] = queue.shift();

        if (preX != -1 && preY != -1) {
          memo[x][y].max = Math.max(memo[x][y].max, grid[x][y] * memo[preX][preY].max, grid[x][y] * memo[preX][preY].min);
          memo[x][y].min = Math.max(memo[x][y].min, grid[x][y] * memo[preX][preY].max, grid[x][y] * memo[preX][preY].min)
        }

        if (x+1 < rows) {
            queue.push([x+1, y, x, y]);
        }
        if (y+1 < cols) {
            queue.push([x, y+1, x, y]);
        }
    }

    return memo[rows-1][cols-1].max >= 0 ? memo[rows-1][cols-1].max % 1000000007 : -1;
}

이 코드는 Max와 Min 값을 저장할 공간인 memo를 선언하는 부분을 제외하고 BFS를 이용한 탐색 부분만을 보여주고 있습니다.

 

BFS탐색을 위한 큐를 선언하고 큐에는 [현재 row, 현재 col, 이전 row, 이전 col] 형식으로 값을 저장합니다. 이전 위치를 같이 큐에 저장하는 이유는 경로의 곱을 계산하기 위함입니다.

 

매 스탭마다, 이전 위치에 대한 memo를 이용하여 현재 위치의 max와 min 값을 업데이트합니다.

 

이 BFS 방식의 문제는 큰 사이즈 grid에서 TLE(시간초과) 가 발생한다는 것입니다. 이 BFS방식에 대해서 생각해보면, 한 셀에 대한 정확한 max와 min값을 알기 위해서는 해당 셀에 두 번의 방문이 필요합니다. 즉, M x N행렬에서 최종 우측 하단의 정확한 max와 min값을 알기 위해서는 어림잡아 O((M x N)^2)의 시간 복잡도가 필요하다는 것을 유추할 수 있습니다.

 

이 문제의 해결을 위해 각 셀을 한번 방문하는 것으로 max와 min 값을 계산할 수 있는 방법을 생각할 수 있습니다.

 

BFS 방식을 다시 한번 자세히 살펴보면, 모든 셀을 2번 방문하는 것은 아니라는 것을 알 수 있습니다. grid의 최 상단 행과 최 좌측 열은 한 번의 방문으로 그 max와 min 값을 알 수 있습니다.

 

이를 이용하면, 나머지 부분에 대해서는 순차적으로 탐색으로 모든 셀의 max와 min값을 알 수 있습니다.

 

이를 코드로 작성하면 다음과 같습니다.

var maxProductPath = function(grid) {
    const row = grid.length;
    const col = grid[0].length;

    let memo = new Array(row).fill(0).map(val => new Array(col).fill(0));
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            memo[i][j] = {h: -Infinity, l: Infinity}
        }
    }

    // 최상단 행과 최좌측 열에 대한 계산
    memo[0][0] = {h: grid[0][0], l: grid[0][0]}
    for (let i = 1; i < col; i++) {
        memo[0][i].h = grid[0][i] * memo[0][i-1].h;
        memo[0][i].l = memo[0][i].h;
    }
    for (let i = 1; i < row; i++) {
        memo[i][0].h = grid[i][0] * memo[i-1][0].h;
        memo[i][0].l = memo[i][0].h;
    }

    // 나머지 부분에 대한 계산
    for (let r = 1; r < row; r++) {
        for (let c = 1; c < col; c++) {
            const h1 = memo[r-1][c].h, h2 = memo[r][c-1].h,
                  l1 = memo[r-1][c].l, l2 = memo[r][c-1].l

            memo[r][c].h = Math.max(h1 * grid[r][c], h2 * grid[r][c], l1 * grid[r][c], l2 * grid[r][c]);
            memo[r][c].l = Math.min(h1 * grid[r][c], h2 * grid[r][c], l1 * grid[r][c], l2 * grid[r][c]);
        }
    }

    return memo[row-1][col-1].h >= 0 ? memo[row-1][col-1].h % 1000000007 : -1;
};

 

Github: 1594.js