C++로 행렬에서 동일한 직사각형 합을 갖는 셀 찾기

문제 개요

이 문제에서는 정수 값으로 이루어진 m×n 크기의 행렬 mat이 주어집니다. 목표는 행렬에서 동일한 직사각형 합을 갖는 셀을 출력하는 프로그램을 작성하는 것입니다.

문제 설명: 행렬 안에서 특정 셀을 찾아야 하며, 그 조건은 해당 셀로 시작하거나 끝나는 부분 행렬들의 합이 나머지 모든 원소의 합과 같아야 한다는 것입니다.

구체적으로 말하면, 셀 (a, b)에 대해 mat[0][0]부터 mat[a][b]까지의 부분 행렬 합과 mat[a][b]부터 행렬의 마지막 셀까지의 부분 행렬 합을 더한 값(이때 겹치는 셀은 한 번만 계산)이 나머지 원소들의 합과 같으면 됩니다.

예제로 문제 이해하기

입력:

mat[][] = { {5, 0, 2, 7},
            {3, 0, 1, 0},
            {1, 4, 1, 3},
            {10, 0, 2, 1}}

출력: (2, 1)

설명:

원소 (2, 1)을 기준으로 살펴보겠습니다.

부분 행렬 1 — (0,0)부터 (2,1)까지:

{ {5, 0},
  {3, 0},
  {1, 4}}

부분 행렬 2 — (2,1)부터 (3,3)까지:

{ {4, 1, 3},
  {0, 2, 1}}

두 부분 행렬의 합(겹치는 셀 (2,1)은 한 번만 계산) = 5 + 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 = 20

나머지 원소들의 합 = 2 + 7 + 1 + 0 + 10 = 20

두 값이 일치하므로 (2, 1)이 조건을 만족하는 셀입니다.

해결 접근 방법

이 문제를 효율적으로 해결하려면 두 개의 보조 행렬 aux1[m][n]과 aux2[m][n]을 생성해야 합니다.

• aux1[i][j]: (0,0)부터 (i,j)까지의 모든 원소의 누적 합을 저장합니다.
• aux2[i][j]: (i,j)부터 행렬의 마지막 셀까지의 모든 원소의 누적 합을 저장합니다.

그다음 각 셀에 대해 두 누적 합을 더한 뒤, 두 영역에서 중복으로 포함된 mat(i,j) 값을 한 번 빼줍니다.

마지막으로 이 값을 행렬 전체 원소의 합(matSum)과 비교합니다. 어떤 셀에서 계산된 합이 행렬 전체 합의 정확히 절반이라면, 즉 matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j])를 만족한다면 해당 셀이 조건을 충족하는 결과 셀이므로 이를 출력합니다.

솔루션 구현 코드

#include <iostream>
using namespace std;
#define R 4
#define C 4

void findCellWithSameRectSum(int mat[R][C]) {
    
    int m = R, n = C;
    int aux1[m][n], aux2[m][n];
    int matSum = 0;
    
    // 초기화: 각 셀 값을 복사하고 전체 합 계산
    for (int i = 0; i < m; i++) {
       for (int j = 0; j < n; j++) {
          
          aux2[i][j] = aux1[i][j] = mat[i][j];
          matSum += mat[i][j];
          
       }
    }

    // 첫 열과 마지막 열 방향 누적합 계산
    for (int i = 1; i < m; i++) {
       
       aux1[i][0] += aux1[i-1][0];
       aux2[m-i-1][n-1] += aux2[m-i][n-1];
    }

    // 첫 행과 마지막 행 방향 누적합 계산
    for (int j = 1; j < n; j++) {
       
       aux1[0][j] += aux1[0][j-1];
       aux2[m-1][n-j-1] += aux2[m-1][n-j];
    }

    // 나머지 셀들의 누적합 계산
    for (int i = 1; i < m; i++)
       for (int j = 1; j < n; j++) {
          
          aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
          aux2[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
       }

    // 조건을 만족하는 셀 탐색 및 출력
    for (int i = 0; i < m; i++)
       for (int j = 0; j < n; j++)
          if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
             cout << "(" << i << ", " << j << ")\t";
}

int main() {
    int mat[R][C] = {{5, 0, 2, 7},
                     {3, 0, 1, 0},
                     {1, 4, 1, 3},
                     {10, 0, 2, 1}};
    cout<<"행렬에서 동일한 직사각형 합을 갖는 셀:\n";
    findCellWithSameRectSum(mat);

    return 0;
}

실행 결과

행렬에서 동일한 직사각형 합을 갖는 셀:
(1, 1)          (2, 1)

위 실행 결과에서 알 수 있듯이, 이 예제 행렬에서는 (1, 1)과 (2, 1) 두 셀이 모두 조건을 만족합니다. 특히 (1, 1)의 값이 0이므로 어느 방향의 부분 행렬에 포함되어도 합에 영향을 주지 않기 때문에 조건을 충족하게 됩니다.

복잡도 분석

• 시간 복잡도: O(m×n) — 행렬을 상수 횟수로 순회하며 누적합을 계산하고 조건을 검사합니다.
• 공간 복잡도: O(m×n) — 두 개의 보조 행렬(aux1, aux2)을 저장하기 위한 추가 공간이 필요합니다.