하나의 행렬(matrix)과 목표값(target)이 주어졌을 때, 합이 목표값과 같은 비어 있지 않은 부분 행렬(submatrix)의 개수를 구하는 문제입니다. 여기서 부분 행렬 [(x1, y1), (x2, y2)]는 x가 x1부터 x2 범위에 있고, y가 y1부터 y2 범위에 있는 모든 셀 matrix[x][y]의 집합을 의미합니다.
두 부분 행렬 [(x1, y1), (x2, y2)]와 [(x1', y1'), (x2', y2')]는 좌표 중 하나라도 다르면 서로 다른 것으로 간주합니다. 예를 들어 x1과 x1'이 같지 않다면 두 부분 행렬은 서로 다릅니다.
예제
입력으로 다음과 같은 행렬이 주어진다고 가정해 보겠습니다.
| 0 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 1 | 0 |
목표값(target)이 0일 때 출력 결과는 4가 됩니다. 그 이유는 0만 포함하는 1x1 크기의 부분 행렬이 정확히 네 개 존재하기 때문입니다.
해결 방법
이 문제는 누적합(prefix sum)과 해시 맵을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
정답 변수 ans를 0으로 초기화합니다.
col에는 열(column)의 개수를, row에는 행(row)의 개수를 저장합니다.
각 행마다 왼쪽에서 오른쪽 방향으로 누적합을 계산합니다. 즉, matrix[i][j]에 matrix[i][j-1]을 더해 해당 행의 구간합을 빠르게 구할 수 있도록 준비합니다.
정수 쌍을 저장할 하나의 맵(map) m을 정의합니다.
두 개의 반복문으로 시작 열 i와 끝 열 j의 모든 조합을 순회합니다.
매 조합마다 맵 m을 초기화하고, m[0]을 1로 설정한 뒤 sum을 0으로 초기화합니다.
각 행 k에 대해 현재 열 구간 [i, j]의 합 current를 계산합니다. i-1이 0 이상이라면 matrix[k][i-1]을 빼서 구간합을 구합니다.
sum에 current를 더한 후, ans에 m[target - sum] 값을 더합니다. 이는 지금까지의 누적합에서 target을 만족하는 이전 누적합의 개수를 의미합니다.
마지막으로 m[-sum] 값을 1 증가시켜 현재 누적합을 기록합니다.
모든 순회가 끝나면 ans를 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int
target) {
int ans = 0;
int col = matrix[0].size();
int row = matrix.size();
for(int i = 0; i < row; i++){
for(int j = 1; j < col; j++){
matrix[i][j] += matrix[i][j - 1];
}
}
unordered_map <int, int> m;
for(int i = 0; i < col; i++){
for(int j = i; j < col; j++){
m.clear();
m[0] = 1;
int sum = 0;
for(int k = 0; k < row; k++){
int current = matrix[k][j];
if(i - 1 >= 0)current -= matrix[k][i - 1];
sum += current;
ans += m[target - sum];
m[-sum]++;
}
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
cout << (ob.numSubmatrixSumTarget(v, 0));
}입력
{{0,1,0},{1,1,1},{0,1,0}}, 0출력
4