1로 구성된 submatrix 합 구하기

황성호·2021년 3월 27일
0

알고리즘

목록 보기
7/7

1로 구성된 submatrix란 위 그림에서 빨간색으로 표시해놓은 1로 구성된 행렬을 의미한다.

submatrix의 합을 구하는 방법은 아래 코드와 같다

var countSquares = function(matrix) {
    let row = matrix.length;
    let column = matrix[0].length;
    
    for(let i=1;i<row;i++) {//(*)
        for(let j=1;j<column;j++) {
            if(matrix[i][j] && matrix[i-1][j] && matrix[i][j-1] && matrix[i-1][j - 1]) {
                matrix[i][j] = Math.min(matrix[i-1][j - 1], matrix[i][j-1], matrix[i-1][j]) + 1;
            }
        }
    }
    let sum = 0;
    
    for(let i=0;i<row;i++) {
        sum += matrix[i].reduce((a,b) => a + b, 0);
    }
    
    return sum;
};

(*)표시된 반복문이 핵심이니 이부분만 설명한다.
[1,1]부터 시작해서 [1,1]'(현재위치), [0,1]'(위), [1,0]'(왼쪽), [0,0]'(왼쪽위)이 모두 0이 아니면 [0,1], [1,0], [0,0]의 최소값+1을 반환한다.

참고
https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/643329/Javascript-solution

profile
개발!

0개의 댓글