문제 소개
m x n 크기의 이진 행렬(binary matrix)이 주어졌을 때, 모든 원소가 1인 정사각형 부분 행렬의 개수를 세는 문제입니다. 예를 들어 다음과 같은 행렬이 있다고 가정해 보겠습니다.
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
이 경우 정사각형은 총 15개가 됩니다. 크기 1x1짜리 정사각형이 10개, 2x2짜리 정사각형이 4개, 그리고 3x3짜리 정사각형이 1개 있는 것입니다.
해결 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이를 저장하는 것입니다. 특정 칸에서의 값이 k라면, 그 칸을 오른쪽 아래 꼭짓점으로 하는 1x1부터 kxk까지 총 k개의 정사각형이 존재한다는 의미입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- ans := 0으로 초기화하고, n := 행(row)의 개수, m := 열(column)의 개수로 설정합니다.
- 마지막 행의 모든 원소를 ans에 더합니다. (i는 0부터 m-1까지)
- 마지막 열의 모든 원소를 ans에 더합니다. (i는 0부터 n-1까지)
- 마지막 행과 마지막 열에서 중복으로 더해진 matrix[n-1][m-1] 값을 한 번 빼줍니다.
- i를 n-2부터 0까지 감소시키며 반복합니다.
- j를 m-2부터 0까지 감소시키며 반복합니다.
- matrix[i][j]가 1이라면, matrix[i][j] := 1 + min(matrix[i+1][j+1], matrix[i][j+1], matrix[i+1][j])로 갱신합니다.
- 그렇지 않으면 matrix[i][j] := 0으로 설정합니다.
- 갱신된 matrix[i][j] 값을 ans에 더합니다.
- j를 m-2부터 0까지 감소시키며 반복합니다.
- 최종적으로 ans를 반환합니다.
여기서 min 연산은 현재 위치의 왼쪽, 위쪽, 대각선(왼쪽 위) 방향의 값을 참조하여, 해당 위치에서 만들 수 있는 최대 정사각형의 크기를 결정합니다. 이렇게 하면 각 칸이 몇 개의 정사각형에 포함되는지 자연스럽게 누적됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int ans = 0;
int n = matrix.size();
int m = matrix[0].size();
for(int i = 0; i < m; i++)ans += matrix[n-1][i];
for(int i = 0; i < n; i++)ans += matrix[i][m-1];
ans -= matrix[n-1][m-1];
for(int i = n - 2;i >= 0; i--){
for(int j = m-2 ;j >= 0; j--){
matrix[i][j] = matrix[i][j] == 1? 1 + min({matrix[i+1][j+1],matrix[i][j+1],matrix[i+1][j]}) : 0;
ans += matrix[i][j];
}
}
return ans;
}
};
main(){
vector<vector<int>> v = {{0,1,1,1},{1,1,1,1},{0,1,1,1}};
Solution ob;
cout << (ob.countSquares(v));
}입력
[[0,1,1,1], [1,1,1,1], [0,1,1,1]]
출력
15
시간 복잡도 분석
이 알고리즘은 행렬의 각 원소를 한 번씩만 방문하므로 시간 복잡도는 O(m x n)입니다. 공간 복잡도 역시 입력 행렬 자체를 DP 테이블로 재활용하기 때문에 추가적인 공간 없이 O(1)의 보조 공간만 사용합니다. 따라서 주어진 행렬을 직접 수정해도 되는 상황이라면 매우 효율적인 해법이라 할 수 있습니다.