C++로 행렬에서 정사각형의 최대 변 길이 찾기

이 문제에서는 크기가 n×n인 2차원 행렬 mat[][]이 주어지며, 여기서 n은 항상 홀수입니다. 우리의 목표는 이 행렬에서 정사각형의 최대 변 길이를 찾는 것입니다.

문제 설명

행렬과 같은 중심을 공유하면서, 테두리(외곽 둘레)에 있는 모든 값이 서로 동일한 정사각형 부분 행렬을 찾고, 그 정사각형의 변 길이를 구해야 합니다.

예시를 통해 문제를 이해해 보겠습니다

입력

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

출력

3

위 예시에서는 중심 (2, 2)를 기준으로 변 길이가 3인 정사각형의 테두리 값이 모두 7로 동일하므로, 정답은 3이 됩니다.

풀이 접근 방식

이 문제를 해결하는 가장 간단한 방법은 먼저 행렬의 중심 원소를 찾는 것입니다. 행렬의 크기가 홀수이므로 중심 원소는 항상 인덱스 (n/2, n/2)에 위치합니다.

중심을 찾은 후에는 중심을 공유하는 다양한 크기의 2차원 부분 행렬(sub-matrix)을 차례대로 검사하면서, 해당 부분 행렬의 테두리에 있는 모든 원소가 동일한 값을 가지는지 확인합니다.

중심에서 i칸 떨어진 부분 행렬의 경우, 테두리는 행 (n/2 − i)와 (n/2 + i), 그리고 열 (n/2 − i)와 (n/2 + i)에 해당하며, 각 행과 열의 인덱스 범위는 (n/2 − i)부터 (n/2 + i)까지입니다. 따라서 i를 0부터 n/2까지 변화시키면서 각 단계마다 부분 행렬의 테두리 원소가 모두 같은지 검사하고, 조건을 만족하는 가장 큰 i에 대해 변 길이(n − 2i)를 결과로 반환하면 됩니다.

솔루션의 동작을 보여주는 프로그램

예제 코드

#include <iostream>
#define n 5
using namespace std;
int findMaxSideSquare(int matrix[][n]) {
    int squareLen = 1;
    for (int i = 0; i < n / 2; i++) {
        int sideVal = matrix[i][i];
        bool isSquare = true;
        for (int j = i; j < n - i; j++) {
            if (matrix[i][j] != sideVal)
                isSquare = false;
            if (matrix[n - i - 1][j] != sideVal)
                isSquare = false;
            if (matrix[j][i] != sideVal)
                isSquare = false;
            if (matrix[j][n - i - 1] != sideVal)
                isSquare = false;
        }
        if (isSquare)
            squareLen = n - 2 * i;
    }
    return squareLen;
}
int main() {
    int mat[n][n] = {
        {2, 4, 6, 6, 5},
        {1, 7, 7, 7, 3},
        {5, 7, 0, 7, 1},
        {3, 7, 7, 7, 1},
        {2, 0, 1, 3, 2}
    };
    cout<<"The maximum side length of square in a Matrix is "<<findMaxSideSquare(mat);
    return 0;
}

실행 결과

The maximum side length of square in a Matrix is 3