이 문제에서는 크기가 n×m인 이진 행렬 bin[][]이 주어지며, 총 q개의 쿼리를 처리해야 합니다. 각 쿼리(x, y)에 대해 모든 원소의 값이 y(0 또는 1)로 동일한 크기 x×x 부분 행렬의 개수를 찾아야 합니다.
문제 설명
주어진 행렬 안에서 두 비트 값 중 하나(0 또는 1)만으로 이루어진, 즉 모든 원소가 같은 값을 갖는 특정 크기의 부분 행렬이 몇 개 있는지 세어야 하는 것이 핵심입니다.
예제로 문제 이해하기
입력
n = 3 , m = 4
bin[][] = {{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
q = 1
q1 = (2, 1)출력
2
해설
크기가 2×2이고 모든 원소가 1로 이루어진 부분 행렬은 다음 위치에서 발견됩니다 −
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}따라서 정답은 2가 됩니다.
풀이 접근법: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 먼저 2차원 배열 DP[][]를 만들어, 각 위치를 끝점으로 하는 '모든 원소가 동일한 최대 부분 행렬'의 크기를 저장합니다. 즉, DP[i][j]는 (i, j)를 오른쪽 아래 끝점으로 하며 모든 원소가 같은 값인 부분 행렬의 한 변 길이를 의미합니다.
예를 들어 DP[4][5] = 2라면, bin[3][4], bin[3][5], bin[4][4], bin[4][5] 네 원소가 모두 같은 값을 가진다는 뜻입니다.
DP[i][j]를 구하는 과정은 두 가지 경우로 나눌 수 있습니다 −
경우 1 − i = 0 또는 j = 0일 때 : 행렬의 첫 번째 행이나 첫 번째 열에 위치하므로 가능한 부분 행렬의 크기가 1뿐입니다. 따라서 DP[i][j] = 1입니다.
경우 2 − 그 외의 경우 : bin[i-(k-1)][j], bin[i][j-(k-1)] 등의 값들을 확인해야 합니다. 일반화하면 DP[i][j] = min(DP[i-1][j], DP[i-1][j-1], DP[i][j-1]) + 1이 성립합니다. k = 2인 경우를 살펴보면, 크기 2×2 부분 행렬을 고려할 때 bin[i][j] = bin[i][j-1] = bin[i-1][j] = bin[i-1][j-1]이 성립하는지 확인하고, 조건을 만족하면 해당 위치의 DP[i][j] 값을 계산합니다.
만약 경우 2의 조건이 충족되지 않으면 기본값으로 DP[i][j] = 1을 설정합니다.
DP[i][j]의 값은 비트가 1(set)인 부분 행렬일 수도 있고 0(unset)인 부분 행렬일 수도 있습니다. 어느 쪽에 속하는지는 bin[i][j]의 값을 확인하면 됩니다. 빈도 정보를 저장하기 위해 두 개의 배열을 생성합니다. zeroFrequency는 0으로 이루어진 부분 행렬의 빈도를, oneFrequency는 1로 이루어진 부분 행렬의 빈도를 저장합니다.
마지막으로 각 크기별 누적 합(suffix sum)을 계산해 두면, 임의의 쿼리(x, y)에 대해 O(1) 시간에 답을 얻을 수 있습니다.
구현 예제
#include <iostream>
using namespace std;
#define N 3
#define M 4
int min(int a, int b, int c) {
if (a <= b && a <= c)
return a;
else if (b <= a && b <= c)
return b;
else
return c;
}
int solveQuery(int n, int m, int bin[N][M], int x, int y){
int DP[n][m], max = 1;
// DP 테이블 채우기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || j == 0)
DP[i][j] = 1;
else if ((bin[i][j] == bin[i - 1][j]) && (bin[i][j] == bin[i][j - 1]) && (bin[i][j] == bin[i - 1][j - 1])) {
DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1;
if (max < DP[i][j])
max = DP[i][j];
}
else
DP[i][j] = 1;
}
}
// 0과 1로 이루어진 부분 행렬의 빈도 계산
int zeroFrequency[n+m] = { 0 }, oneFrequency[n+m] = { 0 };
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (bin[i][j] == 0)
zeroFrequency[DP[i][j]]++;
else
oneFrequency[DP[i][j]]++;
}
}
// 누적 합 계산
for (int i = max - 1; i >= 0; i--) {
zeroFrequency[i] += zeroFrequency[i + 1];
oneFrequency[i] += oneFrequency[i + 1];
}
if (y == 0)
return zeroFrequency[x];
else
return oneFrequency[x];
}
int main(){
int n = 3, m = 4;
int mat[N][M] =
{{ 1, 1, 0, 1},
{ 1, 1, 1, 0},
{ 0, 1, 1, 1}};
int Q = 2;
int query[Q][2] = {{ 2, 1}, { 1, 0}};
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1)<<": The number of Binary sub-matrices of Given size is " <<solveQuery(n, m, mat, query[i][0], query[i][1])<<"\n";
}
return 0;
}출력 결과
For Query 1: The number of Binary sub-matrices of Given size is 2 For Query 2: The number of Binary sub-matrices of Given size is 3
복잡도 분석
DP 테이블을 채우는 데 O(n×m)의 시간이 소요되며, 빈도 배열과 누적 합 계산 역시 O(n+m) 수준입니다. 전처리가 완료된 후에는 각 쿼리를 상수 시간 O(1)에 처리할 수 있어, 쿼리가 많은 경우에도 매우 효율적인 해결 방식입니다.