문제 개요
0과 1로만 채워진 2차원 이진 행렬(binary matrix)이 주어졌을 때, 1로만 구성된 가장 큰 정사각형을 찾아 그 면적을 반환하는 것이 이번 문제의 목표입니다.
예를 들어 다음과 같은 행렬이 주어진 경우를 살펴보겠습니다.
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
이 행렬에서 1로만 이루어진 가장 큰 정사각형은 크기가 2×2이므로, 최종 출력값은 4가 됩니다.
해결 전략: 동적 계획법(Dynamic Programming)
이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 만들 수 있는 정사각형의 최대 한 변의 길이를 저장하는 별도의 DP 테이블을 만드는 것입니다.
알고리즘 단계
ans := 0,n := 행의 개수,c := 열의 개수로 초기화합니다.행렬이 비어 있다면(
n = 0) 즉시 0을 반환합니다.(n × c) 크기의 새로운 DP 행렬을 생성합니다.
원본 행렬의 값을 숫자 형태로 DP 테이블에 복사하면서, 그중 최댓값을
ans에 갱신합니다.행렬의 오른쪽 아래에서 왼쪽 위 방향으로 순회하며, 값이 0이 아닌 칸에 대해 다음 점화식을 적용합니다:
m[i][j] = 1 + min(m[i+1][j], m[i][j-1], m[i+1][j-1])즉, 현재 칸 기준으로 아래쪽, 왼쪽, 왼쪽 아래 대각선 방향의 최솟값에 1을 더한 값이 해당 위치에서 만들 수 있는 최대 정사각형의 한 변 길이입니다.
순회하는 동안
ans를 계속 갱신합니다.최종적으로
ans * ans(한 변의 제곱)를 반환하여 면적을 구합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int ans = 0;
int n = matrix.size();
if(!n)return 0;
int c = matrix[0].size();
vector<vector<int>> m(n, vector <int> (c));
for(int i =0;i<n;i++){
for(int j = 0; j<c;j++){
m[i][j] = matrix[i][j] - '0';
ans = max(m[i][j],ans);
}
}
for(int i =n-2;i>=0;i--){
for(int j =1;j<c;j++){
if(m[i][j]){
m[i][j] = 1 + min({m[i+1][j],m[i][j-1],m[i+1][j-1]});
}
ans = max(ans,m[i][j]);
}
}
return ans*ans;
}
};
main(){
vector<vector<char>> v = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'}, {'1','0','0','1','0'}};
Solution ob;
cout << ((ob.maximalSquare(v)));
}입력
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
출력
4
마무리
이 알고리즘은 시간 복잡도 O(n×c), 공간 복잡도 역시 O(n×c)로, 행렬의 모든 칸을 한 번씩만 순회하므로 매우 효율적입니다. 문자 형태('0', '1')로 입력된 값을 정수로 변환하는 부분(matrix[i][j] - '0')과, 오른쪽 아래부터 거꾸로 순회하며 세 방향의 최솟값을 활용하는 점화식이 핵심 포인트이니 꼭 기억해 두세요.