문제 개요
2차원 행렬이 주어졌을 때, 모든 원소가 동일한 값으로 이루어진 가장 큰 k×k 정사각형 부분 행렬을 찾아 그 크기 k를 구하는 것이 이번 글의 목표입니다.
예를 들어 입력 행렬이 다음과 같다고 가정해 보겠습니다.
| 1 | 1 | 8 | 3 |
| 1 | 5 | 5 | 5 |
| 2 | 5 | 5 | 5 |
| 4 | 5 | 5 | 5 |
위 행렬에는 값 5로만 이루어진 3×3 정사각형이 존재하므로, 정답은 3이 됩니다.
풀이 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
dp[i][j]는 (i, j) 위치를 좌상단 꼭짓점으로 하는, 동일한 값으로 이루어진 정사각형의 최대 크기를 의미합니다.
행렬의 우하단부터 역순으로 순회하면서, 현재 칸의 오른쪽·아래·대각선(우하단) 방향에 있는 원소들이 현재 원소와 같은지 확인합니다.
세 방향 모두 값이 같다면, 세 방향의 dp 값 중 최솟값에 1을 더해 dp[i][j]를 갱신합니다. 하나라도 다르면 더 큰 정사각형을 만들 수 없으므로 해당 값은 0이 됩니다.
알고리즘 단계
n := 행렬의 행 개수
m := 행렬의 열 개수
크기 n×m의 2차원 배열 dp를 선언하고 모든 값을 1로 초기화합니다.
ret := 1 (정답 변수)
i를 n−1부터 0까지 감소시키며 반복합니다.
j를 m−1부터 0까지 감소시키며 반복합니다.
val := 무한대(inf)로 초기화합니다.
i + 1 < n이고 v[i + 1][j] == v[i][j]라면 → val := min(dp[i + 1][j], val), 그렇지 않으면 val := 0
j + 1 < m이고 v[i][j + 1] == v[i][j]라면 → val := min(dp[i][j + 1], val), 그렇지 않으면 val := 0
i + 1 < n이고 j + 1 < m이고 v[i + 1][j + 1] == v[i][j]라면 → val := min(dp[i + 1][j + 1], val), 그렇지 않으면 val := 0
val이 여전히 무한대라면(경계에 있는 마지막 행/열 등) 다음 반복으로 건너뜁니다.
dp[i][j] := dp[i][j] + val 로 갱신하고, ret := max(ret, dp[i][j])로 정답을 업데이트합니다.
모든 순회가 끝나면 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 더 자세히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& v) {
int n = v.size();
int m = v[0].size();
vector<vector<int>> dp(n, vector<int>(m, 1));
int ret = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int val = INT_MAX;
if (i + 1 < n && v[i + 1][j] == v[i][j]) {
val = min(dp[i + 1][j], val);
}
else {
val = 0;
}
if (j + 1 < m && v[i][j + 1] == v[i][j]) {
val = min(dp[i][j + 1], val);
}
else {
val = 0;
}
if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
val = min(dp[i + 1][j + 1], val);
}
else {
val = 0;
}
if (val == INT_MAX)
continue;
dp[i][j] += val;
ret = max(ret, dp[i][j]);
}
}
return ret;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
int main(){
vector<vector<int>> matrix = {
{1, 1, 8, 3},
{1, 5, 5, 5},
{2, 5, 5, 5},
{4, 5, 5, 5}
};
cout << solve(matrix);
}입력
{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5, 5} };출력
3
복잡도 분석
행렬의 모든 칸을 한 번씩만 방문하므로 시간 복잡도는 O(n × m)이며, dp 테이블을 위해 O(n × m)의 추가 공간이 필요합니다. 완전 탐색으로 모든 정사각형을 검사하는 브루트포스 방식(O(n³ × m³))에 비해 상당히 효율적인 접근 방식입니다.