May LeetCoding Challenge[Day21] - Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Input: matrix = [  
[0,1,1,1],  
[1,1,1,1],  
[0,1,1,1] ]
Output: 15
Explanation: There are 10 squares of side 1.
There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 0과 1로 이루어진 m * n 매트릭스가 주어질 때, 사각형이 몇 개인지 찾는 문제이다.

 - 길이가 1인 사각형부터, n인 사각형까지 찾는 문제이다.

 - 처음에 문제를 풀기위해서 생각했던 방법은 재귀함수이다.

 - 2중 for문으로 x,y를 1칸씩 늘려가면서 재귀함수를 이용해 가장 긴 사각형의 길이를 memory 함수에 넣어서 최대 길이를 구해냈다.

 

2. 알고리즘 작성 중, 어려운 점 & 깨달은 점

 

 - 쉬운 난이도의 재귀함수를 풀면서 느끼는 점은 문제에서 주어진 제한 값을 재귀함수에 하나씩 막으면서 풀다보면, 일단 풀긴 풀 수 있는 것 같다.

 

3. 내가 작성한 알고리즘

 

 

class Solution {
    public int countSquares(int[][] matrix) {
        int total=0;
        //0 1 1 1 
		//1 1 2 2 
		//0 1 2 3 
        int memory[][] = new int[matrix.length][matrix[0].length];
        for(int i=0; i<matrix.length; i++){
            for(int j=0;j<matrix[i].length; j++){
                int maxLength = explore(matrix, memory, i, j , 1, matrix.length);
                total += maxLength;
            }
        }
        
        return total;
    }
    
    private int explore(int[][] matrix, int[][] memory, int x, int y, int length, int size){
        if(x < 0 || y < 0){
            return 0;
        }
        if(matrix[x][y] == 0){
            return 0;
        }
        if(memory[x][y] > 0){
            return memory[x][y];
        }
        if(matrix[x][y] == 1 && length == size){
            return 1;
        }
        
        int left = 1 + explore(matrix, memory, x-1, y, length+1, size);
        
        int top = 1 + explore(matrix, memory, x, y-1, length+1, size); 
        
        int leftTop = 1 + explore(matrix, memory, x-1, y-1, length+1, size);
        
        return memory[x][y] = Math.min(left, Math.min(top ,leftTop));
    }
}

 

4. 결과

 

 

5. 작성한 알고리즘 개선하기

 

- memory가 어떻게 저장되는 지, 최종 결과값을 보게 되니

 0 1 1 1

 1 1 2 2

 0 1 2 3

과 같은 아이템을 갖고 있었고, 재귀함수로 maxLength를 구하기보다는 주어진 아이템의 값을 즉시 이용해서 

matrix[i-1][j] matrix[i][j-1] matrix[i-1][j-1]을 검사해서 matrix 배열에 적재해주면 해당 memory를 만들 수 있을 것이라고 생각했다.

 

class Solution {
    public int countSquares(int[][] matrix) {
        int total=0;
        int memory[][] = new int[matrix.length][matrix[0].length];
        for(int i=0; i<matrix.length; i++){
            for(int j=0;j<matrix[i].length; j++){
                int dot = matrix[i][j];
                int min = dot;
                if(dot== 1 && i>0 && j>0){
                    int top = matrix[i][j-1];
                    int left = matrix[i-1][j];
                    int leftTop = matrix[i-1][j-1];    
                    min = Math.min(top, Math.min(left, leftTop));
                    min = Math.max(1, min);
                    if(top>=1 && left>=1 && leftTop >=1){
                        min++;
                        matrix[i][j] = min;
                    }

                }
                total += min;
            }
        }
        
        return total;
    }
}

 

6. 개선한 알고리즘 결과

 

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3336/

Explore - LeetCode