모든 원소가 1인 최대 크기의 정사각형 부분행렬 찾기

문제 개요

0과 1로만 구성된 이진 행렬(binary matrix)이 주어졌을 때, 모든 원소가 1로 이루어진 가장 큰 정사각형 부분행렬을 찾는 것이 이 문제의 목표입니다.

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심은 원본 행렬과 같은 크기의 보조 행렬(size matrix)을 하나 만드는 것입니다. 보조 행렬의 각 칸 Size[i, j]에는 '해당 위치를 오른쪽 아래 꼭짓점으로 하는, 모두 1로 이루어진 정사각형'의 한 변 길이가 저장됩니다. 보조 행렬을 모두 채운 후 최댓값을 구하면, 그 값이 곧 가장 큰 정사각형 부분행렬의 크기가 됩니다.

입력 및 출력

Input:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 1
0 0 0 0 0

Output:
모든 원소가 1로 이루어진 가장 큰 부분행렬

알고리즘

입력 − 원본 이진 행렬

출력 − 모든 원소가 1인 정사각형 중 가장 큰 것을 화면에 출력

subMatWithOne(given matrix)

Begin
    원본 행렬과 같은 크기의 보조 행렬 subMat 을 선언한다
    원본 행렬의 첫 번째 행과 첫 번째 열 값을 subMat 에 복사한다

    for i = 1 to n (모든 행):
        for j = 1 to n (모든 열):
            if matrix[i, j] == 1 then
                subMat[i, j] := 1 + min(subMat[i, j-1],
                                        subMat[i-1, j],
                                        subMat[i-1, j-1])
            else
                subMat[i, j] := 0

    maxSize := subMat[0, 0], iMax := 0, jMax := 0 으로 초기화
    for 모든 i, j:
        if maxSize < subMat[i, j] then
            maxSize := subMat[i, j]
            iMax := i, jMax := j

    행 iMax ~ (iMax - maxSize), 열 jMax ~ (jMax - maxSize) 범위의
    부분행렬을 출력한다
End

동작 원리

현재 위치 (i, j)의 값이 1이라면, 그 위치에서 만들 수 있는 가장 큰 1-정사각형의 크기는 다음 세 방향의 값에 의해 결정됩니다.

• 왼쪽: subMat[i, j-1]
• 위쪽: subMat[i-1, j]
• 대각선 왼쪽 위: subMat[i-1, j-1]

세 값 중 최솟값에 1을 더한 값이 subMat[i, j]가 됩니다. 만약 현재 위치의 값이 0이라면, 그 자리에서 정사각형을 만들 수 없으므로 0을 저장합니다.

시간 복잡도는 O(ROW × COL), 공간 복잡도 역시 O(ROW × COL)로, 행렬의 크기에 비례하는 선형 시간 안에 해를 구할 수 있습니다.

C++ 구현 예제

#include<iostream>
#define ROW 6
#define COL 5
using namespace std;

int matrix[ROW][COL] = {
    {0, 1, 1, 0, 1},
    {1, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 0, 0}
};

// 세 값 중 최솟값을 반환하는 함수
int min(int a, int b, int c) {
    return ((a<b?a:b))?((a<c)?a:c):((b<c)?b:c);
}

void subMatWithOne() {
    int subMat[ROW][COL];
    int maxSize, iMax, jMax;

    for(int i = 0; i < ROW; i++)   // 행렬의 첫 번째 열을 보조 행렬에 복사
        subMat[i][0] = matrix[i][0];

    for(int j = 0; j < COL; j++)   // 행렬의 첫 번째 행을 보조 행렬에 복사
        subMat[0][j] = matrix[0][j];

    for(int i = 1; i < ROW; i++) {
        for(int j = 1; j < COL; j++) {
            if(matrix[i][j] == 1)  // 왼쪽, 위쪽, 대각선 값의 최솟값 + 1
                subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
            else
                subMat[i][j] = 0;  // 값이 0이면 그대로 0 저장
        }
    }

    maxSize = subMat[0][0]; iMax = 0; jMax = 0;
    for(int i = 0; i < ROW; i++) {   // 가장 큰 정사각형의 크기와 위치 탐색
        for(int j = 0; j < COL; j++) {
            if(maxSize < subMat[i][j]) {
                maxSize = subMat[i][j];
                iMax = i;
                jMax = j;
            }
        }
    }

    cout << "Subsquare matrix: "<<endl;
    for(int i = iMax; i > iMax - maxSize; i--) {   // 최대 크기를 이용해 부분행렬 출력
        for(int j = jMax; j > jMax - maxSize; j--) {
            cout << matrix[i][j]<<" ";
        }
        cout << endl;
    }
}

int main() {
    subMatWithOne();
}

실행 결과

Subsquare matrix:
1 1 1
1 1 1
1 1 1

실행 결과에서 확인할 수 있듯이, 주어진 행렬에서 모든 원소가 1로 이루어진 가장 큰 정사각형은 3×3 크기입니다. 이처럼 보조 행렬을 활용한 동적 계획법을 사용하면 모든 가능한 정사각형을 일일이 검사하는 브루트 포스 방식(O(n³) 이상)보다 훨씬 빠르게 답을 구할 수 있습니다.