JavaScriptでバイナリ行列内の最も近い0までの距離を求めるアルゴリズム

バイナリ行列とは、0 または 1 のみを要素として持つ配列（配列の配列）のことです。本記事では、JavaScript を使って、与えられたバイナリ行列に対し「各セルから最も近い 0 までの距離」を格納した新しい行列を作成する関数を実装する方法を解説します。

問題の概要

今回実装する JavaScript 関数は、バイナリ行列を唯一の引数として受け取り、以下の条件を満たす新しい行列を返します。

• 元の行列と同じ行数・列数を持つ
• 各セルには、元の行列におけるその位置から最も近い 0 までの距離が格納される
• 距離の計算は上下左右（水平・垂直）方向のみで移動できるものとし、斜め移動は考慮しない（マンハッタン距離）
• 元の行列には必ず少なくともひとつの 0 が含まれることが保証されている

入出力の例

たとえば、次のような入力行列が与えられたとします。

const arr = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1],
];

この場合、期待される出力は次のとおりです。

const output = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 2, 1],
];

出力を見ると、たとえば右下の [2][1] のセルは、真上にある 0 との距離が 2 であるため 2 が格納されています。このように、各セルごとに上下左右への移動回数として最短距離が計算されます。

解法のアプローチ：BFS（幅優先探索）

この問題は、グラフ理論におけるマルチソース幅優先探索（Multi-source BFS）として捉えることができます。手順は以下のとおりです。

1. 初期化： 結果行列 res を作成する。0 のセルには 0 を、それ以外には大きな値（Number.MAX_SAFE_INTEGER）を仮に設定する。同時に、0 の座標をすべてキュー（配列）に登録する。
2. 探索： キューが空になるまで、キューから座標を取り出し、その上下左右の隣接セルを確認する。
3. 更新： 隣接セルの現在の距離が「現在のセルの距離 + 1」より大きい場合、より短い経路が見つかったことになるので値を更新し、そのセルを次のキューに追加する。
4. 繰り返し： 更新がなくなるまでこれを続けると、すべてのセルに正しい最短距離が確定する。

BFS では近いレベル（距離）のセルから順番に処理されるため、各セルに最初に到達した時点の距離が自動的に最短距離となります。

コード例

実際のコードは以下のとおりです。

const arr = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1],
];

const findNearestDistance = (arr = []) => {
    let array = [];
    // 初期化：0 のセルは距離 0、それ以外は最大値で埋める
    let res = arr.map((el, ind) => el.map((subEl, subInd) => {
        if (subEl === 0) {
            array.push([ind, subInd]);
            return 0;
        }
        return Number.MAX_SAFE_INTEGER;
    }));

    // 隣接セルの距離を更新するヘルパー関数
    const updateAdjacent = (ind, subInd, min, next = []) => {
        if (
            ind < 0 || subInd < 0 ||
            ind == arr.length || subInd == arr[0].length
        ) {
            return; // 行列の範囲外は無視
        }
        if (res[ind][subInd] < min + 2) return; // 既により短い距離がある
        res[ind][subInd] = min + 1;
        next.push([ind, subInd]);
    };

    // BFS：キューが空になるまで波状に更新を広げる
    while (array.length) {
        let next = [];
        for (let [ind, subInd] of array) {
            updateAdjacent(ind, subInd + 1, res[ind][subInd], next); // 右
            updateAdjacent(ind, subInd - 1, res[ind][subInd], next); // 左
            updateAdjacent(ind + 1, subInd, res[ind][subInd], next); // 下
            updateAdjacent(ind - 1, subInd, res[ind][subInd], next); // 上
        }
        array = next;
    }

    return res;
};

console.log(findNearestDistance(arr));

コードのポイント解説

• res の初期化時に、0 のセルの座標をすべてキュー array に集めています。これがマルチソース BFS の起点になります。
• updateAdjacent は境界チェックを行い、範囲外なら何もせず、既存の値が現在地 + 1 未満なら更新をスキップします。これにより不要な再計算を防いでいます。
• while ループの中では、現在のキューの各セルについて 4 方向の隣接セルをチェックし、更新されたセルだけを次のキュー next に入れます。これにより距離が 1 ずつ波のように広がっていきます。

実行結果

コンソールに出力される結果は次のとおりです。

[ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 1, 2, 1 ] ]

計算量について

• 時間計算量： O(m × n)。各行・各セルは最大でも定数回（4 方向 × 各セル）処理されるため、行列全体を線形時間で処理できます。
• 空間計算量： O(m × n)。結果行列とキューのための領域が必要です。

全セル同士のペアで距離を直接計算する素朴な方法だと O((m×n)²) かかってしまいますが、BFS を使うことで効率的に解けるのがこの手法の大きな利点です。