C++로 풀어보는 행렬 블록 합(Matrix Block Sum) 문제

문제 개요

m × n 크기의 행렬 mat과 정수 K가 주어졌을 때, 새로운 행렬 answer를 만들어야 합니다. 이때 각 원소 answer[i][j]는 다음 조건을 만족하는 모든 mat[r][c] 값의 합입니다.

i − K ≤ r ≤ i + K
j − K ≤ c ≤ j + K
(r, c)는 행렬 내부의 유효한 위치

즉, 각 위치를 기준으로 K만큼 떨어진 범위(정사각형 영역)에 포함된 원소들을 모두 더한 값을 결과 행렬에 저장하는 것입니다.

입력 예시

다음과 같은 3×3 행렬이 주어지고,

1	2	3
4	5	6
7	8	9

K = 1일 때 출력 결과는 다음과 같습니다.

12	21	16
27	45	33
24	39	28

예를 들어 왼쪽 위 모서리인 answer[0][0]은 자기 자신(1)과 인접한 오른쪽(2), 아래쪽(4), 대각선(5)의 합인 12가 됩니다. 행렬 경계를 벗어나는 위치는 계산에서 제외됩니다.

해결 방법

이 문제는 브루트포스 방식으로 해결할 수 있습니다. 단계별 접근은 다음과 같습니다.

n := 행의 개수, m := 열의 개수로 설정합니다.
n × m 크기의 결과 행렬 ans를 선언합니다.
i를 0부터 n−1까지 반복합니다.
- j를 0부터 m−1까지 반복합니다.
  - r을 i−k부터 i+k까지 반복합니다.
    - c를 j−k부터 j+k까지 반복하며,
      - r과 c가 행렬의 유효한 인덱스 범위 안에 있다면 ans[i][j] += mat[r][c]를 수행합니다.
모든 반복이 끝나면 ans를 반환합니다.

시간 복잡도는 O(n × m × k²)이며, K가 작은 경우 충분히 실용적입니다. 참고로 누적합(prefix sum) 기법을 활용하면 O(n × m)까지 최적화할 수 있습니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i < v.size(); i++){
      cout << "[";
      for(int j = 0; j < v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}
class Solution {
public:
   vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
      int n = mat.size();
      int m = mat[0].size();
      vector<vector<int>> ans(n, vector<int>(m));
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            for(int r = i - k; r <= i + k; r++){
               for(int c = j - k; c <= j + k; c++){
                  if(r >= 0 && r < n && c >= 0 && c < m){
                     ans[i][j] += mat[r][c];
                  }
               }
            }
         }
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v1 = {{1,2,3},{4,5,6},{7,8,9}};
   Solution ob;
   print_vector(ob.matrixBlockSum(v1, 1));
}

입력

[[1,2,3],[4,5,6],[7,8,9]]
1

출력

[[12, 21, 16], [27, 45, 33], [24, 39, 28]]

마무리

행렬 블록 합 문제는 이중 반복문과 범위 검사만으로 직관적으로 해결할 수 있는 대표적인 배열 순회 문제입니다. 경계 조건 처리가 핵심이며, 더 나아가 2차원 누적합을 응용하면 성능을 크게 향상시킬 수 있으므로 추가 학습에 좋은 소재입니다.