C++でブール行列における最大領域のサイズを求める方法

はじめに

この記事では、0と1のみで構成される n×m の2次元行列(ブール行列)が与えられたとき、その中で最も大きな「領域」のサイズを求める方法を解説します。

問題の概要

値が 1 のセルは「塗りつぶしセル」とみなされます。塗りつぶしセル同士が水平方向・垂直方向・斜め方向のいずれかで隣接している場合、それらは同じ領域に属すると判断します。私たちのタスクは、こうして連結したセルの数が最大となる領域の大きさ(セル数)を求めることです。

具体例で理解しよう

入力: matrix[4][5]

{ {0, 1, 1, 0, 1},
  {0, 0, 1, 1, 1},
  {1, 0, 0, 0, 0},
  {1, 0, 1, 0, 1} }

出力: 6

説明: この行列には複数の連結領域が存在し、それぞれのサイズは 1、2、6 です。したがって、最大領域の長さは 6 となります。

解法のアプローチ

この問題は、行列内で互いに連結しているセルの総数を数えることで解決できます。具体的には、次の手順で進めます。

1. 行列の各セルを順番に走査します。
2. まだ訪問していない塗りつぶしセル(値が 1 のセル)を見つけたら、そこを起点として DFS(深さ優先探索)を実行します。
3. DFS では、現在のセルの周囲 8 方向(上下左右と斜め)の隣接セルをすべてチェックし、未訪問の塗りつぶしセルがあれば再帰的に探索を続けます。
4. 訪問済みのセルは bool 型の visited 配列で管理し、同じセルを二度カウントしないようにします。
5. 各領域の探索が完了したらセル数を記録し、最終的にその最大値を返します。

C++での実装例

上記のアプローチを実装したC++プログラムが以下です。

#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5

// 指定セルが範囲内かつ未訪問の塗りつぶしセルかどうかを判定
int isNotVisited(int M[][COL], int row, int col, bool visited[][COL]) {
    return (row >= 0) && (row < ROW) && (col >= 0 ) && (col < COL) && (M[row][col] && !visited[row][col]);
}

// 深さ優先探索(DFS)で連結領域のセル数をカウント
void depthFirstSearch(int M[][COL], int row, int col, bool visited[][COL], int& count){
    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
    visited[row][col] = true;

    for (int k = 0; k < 8; ++k) {
        if (isNotVisited(M, row + rowNbr[k], col + colNbr[k], visited)) {
            count++;
            depthFirstSearch(M, row + rowNbr[k], col + colNbr[k], visited, count);
        }
    }
}

// 最大領域の長さを求める関数
int findLargestRegionLength(int M[][COL]) {
    bool isvisited[ROW][COL];
    memset(isvisited, 0, sizeof(isvisited));
    int maxCount = -1;
    for (int i = 0; i < ROW; ++i) {
        for (int j = 0; j < COL; ++j) {
            if (M[i][j] && !isvisited[i][j]) {
                int count = 1;
                depthFirstSearch(M, i, j, isvisited, count);
                maxCount = max(maxCount, count);
            }
        }
    }
    return maxCount;
}

int main(){
    int M[][COL] = { {0, 1, 1, 0, 1},
                     {0, 0, 1, 1, 1},
                     {1, 0, 0, 0, 0},
                     {1, 0, 1, 0, 1} };

    cout<<"The length of largest region is "<<findLargestRegionLength(M);

    return 0;
}

出力結果

The length of largest region is 6

計算量について

このアルゴリズムでは、各セルを高々一度しか訪問しないため、時間計算量は O(n×m) です。また、訪問状態を管理するための配列が必要となるため、空間計算量も O(n×m) となります。