LeetCode 1277 - Count Square Submatrices with All Ones

 

안녕하세요 besforyou 입니다

이번 글에서는 LeetCode 문제 1277번 풀이를 써보겠습니다

---

문제 풀이

 

방법 1.  그냥 다 찾아보는 방법

 

정사각형의 개수를 찾아야 하는 문제이다.

 

우선 m과 n 중 작은 숫자를 min_side라고 하고, 한 변의 길이가 1인 정사각형부터 한 변의 길이가 min_side인 정사각형을 2차원 배열에서 다 찾아본다. 

 

2차원 배열 안에서 인덱스 i, j를 정사각형의 왼쪽 위 꼭지점이라고 가정하고 한 변의 길이가 l이라고 가정하자

 

그러면 i, j ~ i, j+l  /  i + l , j ~ i + l , j + l /  i , j + l ~ i + l , j + l 안쪽의 숫자가 모두 1이면 정사각형인 것이다. 이를 반복문으로 구현한다.

 

코드

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        
        int n = matrix.size();  // rows
        int m = matrix[0].size(); // column
        
        int ans = 0;
        
        int min_side = min(n,m);
        
        for (int len = 1 ; len <= min_side ; len++) 
            ans += counter(matrix, len, n, m);
        
        return ans;
    }
    
    int counter(vector<vector<int>>& matrix, int side, int n, int m) {
        
        int count = 0;
     
        for (int i = 0; i <= n - side ; i++) {
            for (int j = 0; j <= m - side ; j++) {
                if ( checker(matrix, i, j, side ) )
                    count++;
            }
        }
        
        return count;
    }
    
    bool checker(vector<vector<int>> & matrix, int i, int j , int side) {
        int temp = j;
        for (int a = 0; a < side ; a++) {
            j = temp;
            for (int b = 0 ; b < side ; b++) {
                if ( matrix[i][j] == 0) 
                    return false;
                j += 1;
            }
            i += 1;
        }
        
        return true;
    }
};

 

성공은 한다. 하지만 효율적인 알고리즘이라고는 할 수 없다.

 

 

 

방법 2.  Dynamic Programming ( 동적 계획법 )

 

과거의 계산을 현재의 계산에 사용하자.

 

dp[i][j]에 A[i][j]를 사각형의 오른쪽 아래 꼭지점으로 가지는 가장 큰 사각형의 크기를 저장한다.

dp[i][j]는 A[i][j]를 사각형의 오른쪽 아래 꼭지점으로 가지는 사각형의 개수를 의미하기도 함

 

 

코드

 

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int result = 0;
        
        for(int i = 0; i<matrix.size(); i++)
        {
            for(int j = 0; j<matrix[0].size(); j++)
            {
                if(i > 0 && j > 0 && matrix[i][j]>0)
                    matrix[i][j] = min(matrix[i-1][j-1], min(matrix[i-1][j], matrix[i][j-1])) + 1;
                
                result += matrix[i][j];
            }
        }
        
        return result;
    }
};

 

 

결과