C++로 행렬에서 모래시계(Hourglass) 최대 합 구하기

이 문제에서는 하나의 행렬(matrix)이 주어지며, C++을 사용해 행렬 안에서 만들 수 있는 모래시계(hourglass) 모양 요소들의 최대 합을 찾는 프로그램을 작성하는 것이 목표입니다.

문제 설명

주어진 행렬의 요소들로 만들 수 있는 모든 모래시계의 합을 계산하고, 그중 가장 큰 값을 찾습니다.

모래시계란 행렬에서 다음과 같은 형태를 가지는 7개의 요소로 이루어진 도형을 말합니다.

X X X
  X
X X X

예제로 이해하기

입력 −

array = {
   {2 4 0 0}
   {0 1 1 0}
   {4 2 1 0}
   {0 3 0 1}}

출력 − 14

설명 − 이 행렬에서 만들 수 있는 모래시계는 다음과 같습니다.

2 4 0        0 1 1
  1            2
4 2 1        0 3 0

4 0 0        1 1 0
  1            1
2 1 0        3 0 1

모래시계의 인덱스 구조

모래시계는 다음과 같은 인덱스 조합으로 구성됩니다.

matrix[i][j]     matrix[i][j+1]     matrix[i][j+2]
                 matrix[i+1][j+1]
matrix[i+2][j]   matrix[i+2][j+1]   matrix[i+2][j+2]

즉, 시작 위치 [0][0]부터 [행-3][열-3]까지 각 지점에서 위와 같은 인덱스 조합으로 모래시계를 만들 수 있습니다. 각 시작점에서 생성되는 모래시계의 합을 모두 계산한 뒤, 그중 최댓값(maxSum)을 구하면 됩니다.

구현 예제

다음은 해결 방법의 동작을 보여주는 프로그램입니다.

#include<iostream>
using namespace std;
const int row = 4;
const int col = 4;

int findHourGlassSum(int mat[row][col]){
    if (row < 3 || col < 3)
        return -1;
    int maxSum = 0;
    for (int i = 0; i < row - 2; i++){
        for (int j = 0; j < col - 2; j++){
            int hrSum = (mat[i][j] + mat[i][j+1] + mat[i][j+2])
                      + (mat[i+1][j+1])
                      + (mat[i+2][j] + mat[i+2][j+1] + mat[i+2][j+2]);
            maxSum = max(maxSum, hrSum);
        }
    }
    return maxSum;
}

int main() {
    int mat[row][col] = {
        {2, 4, 0, 0},
        {0, 1, 1, 0},
        {4, 2, 1, 0},
        {0, 3, 0, 1}};
    int maxSum = findHourGlassSum(mat);
    if (maxSum == -1)
        cout << "Not possible";
    else
        cout << "Maximum sum of hour glass created is " << maxSum;
    return 0;
}

출력 결과

Maximum sum of hour glass created is 14

동작 원리 및 성능 분석

이 알고리즘은 행렬 내에서 모래시계를 배치할 수 있는 모든 시작점을 이중 반복문으로 탐색합니다. 각 시작점마다 7개 요소의 합을 계산하고, 기존 최댓값과 비교해 더 큰 값을 저장하는 방식입니다. 전체 시간 복잡도는 O(R×C)이며, 추가 배열 없이 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.

참고로, 행렬의 모든 요소가 음수인 경우에는 maxSum의 초기값을 0 대신 INT_MIN(climits 헤더)으로 설정하는 것이 더 안전합니다. 또한 행렬의 크기가 3×3보다 작으면 모래시계를 만들 수 없으므로, 함수 초반에 이를 검사해 -1을 반환하도록 처리했습니다.