C++で解くブール行列の更新問題：1がある行と列をすべて1にする方法

ここでは、興味深いブール行列の問題を取り上げます。0と1のみで構成されたブール行列が与えられ、その中で「1」がマークされている位置を見つけることが目的です。もし位置 mat[i][j] に 1 が存在するならば、i 行目と j 列目のすべての要素を 1 に変更します。

具体例を見てみましょう。次のような行列が与えられたとします。

1 0 0 1
0 0 0 0
0 0 0 0
0 1 0 0

この行列に対して処理を実行すると、結果は以下のようになります。

1 1 1 1
1 1 0 1
1 1 0 1
1 1 1 1

(0,0) と (0,3)、そして (3,1) の位置に 1 があったため、それらの行と列全体が 1 で埋められているのが分かります。

アルゴリズム

matrixUpdate(matrix[R][C])

この問題を効率的に解くには、補助的な配列を2つ用意するのがポイントです。手順は以下の通りです。

begin
    サイズRの配列 row[] とサイズCの配列 col[] を定義し、すべて0で初期化する
    mat[R][C] を走査し、1が存在する位置の行インデックスを row[] に、
    列インデックスを col[] に記録（マーク）する
    row[] と col[] を確認し、マークされている行・列の全要素を1で埋める
end

このアプローチにより、元の行列を直接書き換える前に「どの行・列を更新すべきか」という情報を保持できるため、更新処理が他のセルの判定に影響を与えることを防げます。計算量は O(R×C)、補助記憶域は O(R+C) となります。

C++による実装例

#include <iostream>
#define R 4
#define C 4
using namespace std;

void updateMatrix(bool mat[R][C]) {
    bool row[R];
    bool col[C];
    int i, j;

    // row配列の全要素を0で初期化
    for (i = 0; i < R; i++) {
        row[i] = 0;
    }

    // col配列の全要素を0で初期化
    for (j = 0; j < C; j++) {
        col[j] = 0;
    }

    // 1が存在する位置の行・列をマークする
    for (i = 0; i < R; i++) {
        for (j = 0; j < C; j++) {
            if (mat[i][j] == 1) {
                row[i] = 1;
                col[j] = 1;
            }
        }
    }

    // マークされた行・列の全要素を1に設定する
    for (i = 0; i < R; i++) {
        for (j = 0; j < C; j++) {
            if (row[i] == 1 || col[j] == 1) {
                mat[i][j] = 1;
            }
        }
    }
}

void displayMatrix(bool mat[R][C]) {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << mat[i][j];
        }
        cout << endl;
    }
}

int main() {
    bool mat[R][C] = { {1, 0, 0, 1},
                       {0, 0, 0, 0},
                       {0, 0, 0, 0},
                       {0, 1, 0, 0} };

    cout << "Given Matrix" << endl;
    displayMatrix(mat);

    updateMatrix(mat);

    cout << "Updated Matrix" << endl;
    displayMatrix(mat);

    return 0;
}

実行結果

Given Matrix
1001
0000
0000
0100
Updated Matrix
1111
1101
1101
1111

まとめ

この問題は、補助配列 row[] と col[] を使うことで、シンプルかつ効率的に解くことができます。行列を一度走査して 1 の位置を記録し、もう一度走査して該当する行・列を更新するという2パス方式が鍵となります。計算量は O(R×C) であり、追加メモリも O(R+C) に抑えられるため、大規模な行列に対しても実用的な手法です。