C++로 합이 K와 같은 가장 큰 면적의 직사각형 부분 행렬 찾기

문제 개요

2차원 행렬 mat과 값 K가 주어졌을 때, 원소들의 합이 정확히 K와 같으면서 면적이 가장 넓은 직사각형 부분 행렬(submatrix)을 찾는 것이 목표입니다.

예를 들어 다음과 같은 4×4 행렬이 있다고 가정해 보겠습니다.

여기서 K = 9라면, 답은 왼쪽 위 좌표가 (1, 0), 오른쪽 아래 좌표가 (3, 2)인 부분 행렬입니다.

실제로 이 부분 행렬의 합은 (-7) + 7 + 8 + 11 + (-14) + 4 + (-4) + 3 + 1 = 9로 조건을 만족하며, 이보다 더 넓은 면적의 부분 행렬 중 합이 9인 것은 존재하지 않습니다.

해결 접근 방식

이 문제는 두 단계로 나누어 해결할 수 있습니다.

1단계: 1차원 배열에서 합이 K인 가장 긴 구간 찾기

먼저 sum_k() 함수는 1차원 배열에서 누적합(prefix sum)과 해시 맵(unordered_map)을 활용하여 합이 K가 되는 가장 긴 연속 구간을 O(n) 시간에 찾습니다. 알고리즘 흐름은 다음과 같습니다.

• 누적합 sum과 최대 길이 maximum_length를 초기화합니다.
• 각 인덱스 i에 대해 누적합을 갱신합니다.
• 누적합이 처음부터 현재까지의 합으로 곧바로 K와 같다면, 구간 [0, i]가 후보가 됩니다.
• 누적합 값을 맵에 처음 등장하는 경우에만 저장합니다(가장 긴 구간을 만들기 위해 가장 이른 위치를 기록).
• sum - k가 맵에 존재한다면, 그 위치 다음 인덱스부터 현재 인덱스까지의 구간 합이 K가 되므로, 기존 최대 길이와 비교하여 갱신합니다.
• 최대 길이가 0이 아니면 유효한 구간이 존재한다는 의미로 true를 반환합니다.

2단계: 열 쌍을 고정하며 2차원 문제를 1차원으로 축소

메인 로직에서는 모든 왼쪽 열(left)과 오른쪽 열(right)의 조합에 대해 다음을 수행합니다.

• 각 행마다 left ~ right 범위의 열 값을 누적한 임시 배열 temp를 유지합니다.
• temp 배열에 대해 1단계 함수를 호출하여 합이 K인 가장 긴 행 구간(up ~ down)을 구합니다.
• 면적 = (down - up + 1) × (right - left + 1)을 계산하고, 기존 최대 면적보다 크면 좌표와 면적을 갱신합니다.

모든 탐색이 끝난 뒤 결과 좌표가 초기값 {0,0,0,0} 그대로이고 mat[0][0]도 K가 아니라면, 조건을 만족하는 부분 행렬이 없다는 메시지를 출력합니다.

전체 시간 복잡도는 열 쌍 선택에 O(col²), 각 열 쌍마다 1차원 탐색에 O(row)가 소요되므로 O(col² × row)입니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;

bool sum_k(int arr[], int& start, int& end, int n, int k) {
    unordered_map<int, int> map;
    int sum = 0, maximum_length = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum == k) {
            maximum_length = i + 1;
            start = 0;
            end = i;
        }
        if (map.find(sum) == map.end())
            map[sum] = i;
        if (map.find(sum - k) != map.end()) {
            if (maximum_length < (i - map[sum - k])) {
                maximum_length = i - map[sum - k];
                start = map[sum - k] + 1;
                end = i;
            }
        }
    }
    return (maximum_length != 0);
}

void sum_zero(vector<vector<int>> &mat, int k) {
    int row = mat.size();
    int col = mat[0].size();
    int temp[row], area;
    bool sum;
    int up, down;
    vector<int> final_point = {0,0,0,0};
    int maxArea = INT_MIN;

    for (int left = 0; left < col; left++) {
        memset(temp, 0, sizeof(temp));
        for (int right = left; right < col; right++) {
            for (int i = 0; i < row; i++)
                temp[i] += mat[i][right];
            sum = sum_k(temp, up, down, row, k);
            area = (down - up + 1) * (right - left + 1);
            if (sum && maxArea < area) {
                final_point[0] = up;
                final_point[1] = down;
                final_point[2] = left;
                final_point[3] = right;
                maxArea = area;
            }
        }
    }

    if (final_point[0] == 0 && final_point[1] == 0 && final_point[2] == 0 &&
    final_point[3] == 0 && mat[0][0] != k) {
        cout << "No sub-matrix found";
        return;
    }

    cout << "(Top, Left) Coordinate: " << "(" << final_point[0] << ", " << final_point[2] << ")" << endl;
    cout << "(Bottom, Right) Coordinate: " << "(" << final_point[1] << ", " << final_point[3] << ")" << endl;

    for (int j = final_point[0]; j <= final_point[1]; j++) {
        for (int i = final_point[2]; i <= final_point[3]; i++)
            cout << mat[j][i] << " ";
        cout << endl;
    }
}

main(){
    vector<vector<int>> v = {
        { 2, 8, -5, 6 },
        { -7, 7, 8, -3 },
        { 11, -14, 4, 3 },
        { -4, 3, 1, 10 }};
    sum_zero(v, 9);
}

입력

{{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }},
9

출력

(Top, Left) Coordinate: (1, 0)
(Bottom, Right) Coordinate: (3, 2)
-7 7 8
11 -14 4
-4 3 1

정리

이 알고리즘은 음수를 포함한 행렬에서도 동작한다는 점이 핵심입니다. 양수만 포함된 행렬이라면 투 포인터 기법으로 더 효율적으로 풀 수 있지만, 음수가 섞여 있으면 누적합과 해시 맵을 결합한 방식이 필수적입니다. 열 쌍을 고정하고 1차원 문제로 환원하는 이 패턴은 '최대 합 직사각형', '목표 합 부분 행렬' 등 다양한 변형 문제에도 그대로 적용할 수 있으므로 잘 익혀두면 유용합니다.