【C++】2値行列から「すべて1」の最大正方形部分行列を求める動的計画法

0と1だけで構成された2値行列(バイナリ行列)が与えられたとき、その中から「すべての要素が1である正方形部分行列」のうち最も大きいものを見つけるのが、本記事で扱う問題です。

この問題は動的計画法(DP)を用いることで効率的に解くことができます。まず、元の行列と同じ大きさの補助的な「サイズ行列」を作成します。このサイズ行列の各要素 Size[i, j] には、「セル (i, j) を右下とする、すべて1で構成される正方形の一辺の長さ」を記録していきます。サイズ行列が完成した後、その中の最大値を調べることで、最大の正方形部分行列のサイズと位置を特定できます。

入力と出力

入力:2値行列
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

出力:
すべてが1で構成される最大の部分行列

アルゴリズム

subMatWithOne(与えられた行列)

入力 − 元となる2値行列。

出力 − 最大の「すべて1」の正方形行列を表示する。

Begin
    与えられた行列と同じ大きさの subMat を定義する
    行列の最初の行と最初の列を subMat にコピーする

    各行 i (1 から n) に対して繰り返す
        各列 j (1 から n) に対して繰り返す
            もし matrix[i, j] = 1 ならば
                subMat[i, j] := 1 + ( subMat[i, j-1](左)、
                subMat[i-1, j](上)、subMat[i-1, j-1](左上)の最小値 )
            そうでなければ
                subMat[i, j] := 0
        繰り返し終了
    繰り返し終了

    maxSize := subMat[0, 0]、iMax := 0、jMax := 0 で初期化
    すべての行 i・列 j に対して繰り返す
        もし maxSize < subMat[i, j] ならば
            maxSize := subMat[i, j]
            iMax := i、jMax := j
    繰り返し終了

    行 = iMax から (iMax − maxSize)、
    列 = jMax から (jMax − maxSize) の範囲の部分行列を表示
End

ポイント:漸化式の意味

セル (i, j) が1のとき、そこを右下とする正方形の一辺の長さは、「左」「上」「左上」の3つのセルの値の最小値 + 1 となります。これは、周囲3方向のいずれかでもっとも小さい正方形に合わせて拡張できるためです。セルが0の場合は、当然ながら正方形を形成できないため0を代入します。計算量は 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}
};

// 3つの値の最小値を返す関数
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 << "部分正方形行列:" << 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();
}

実行結果

部分正方形行列:
1 1 1
1 1 1
1 1 1

このように、与えられた6×5の2値行列の中から、一辺3の「すべて1」の正方形部分行列が見つかりました。サイズ行列を使ったDPアプローチにより、総当たり(O(n³)以上)よりも大幅に高速に解ける点が、このアルゴリズムの大きな魅力です。