【JavaScript】腐ったトマトが全体に広がるまでの最小時間を求める問題をBFSで解く

問題概要

数値の2次元配列 arr を唯一の引数として受け取る JavaScript の関数を作成します。配列の各セルには、以下のいずれかの値が格納されています。

• 0 … 空のセル
• 1 … 新鮮なトマト
• 2 … 腐ったトマト

毎分、腐ったトマトと上下左右（4方向）で隣接している新鮮なトマトは腐っていきます。

この関数は、新鮮なトマトが1つも残らなくなるまでにかかる最小の経過時間（分）を返す必要があります。もしすべてのトマトを腐らせることが不可能な場合は、代わりに -1 を返してください。

入力例

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

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

const output = 4;

出力の解説

腐敗は毎分1段階ずつ隣接する新鮮なトマトへ広がり、この例では4分ですべてのトマトが腐ります。経過時間ごとのグリッドの状態変化は以下の通りです。

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

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

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

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

実装コード（BFSによる解法）

この種の「感染が広がっていく」問題は、幅優先探索（BFS）を使うことで効率的に解けます。考え方はシンプルで、まず新鮮なトマトの総数と、初期状態で腐っているトマトの座標をすべて記録します。その後、腐ったトマトを起点（複数のスタート地点）として、1分ごとに一斉に腐敗を周囲へ広げていくイメージです。

const arr = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1]
];
const timeToRot = (arr = []) => {
    let fresh = 0;
    let count = -1;
    let curr = [];
    // 初回スキャン：新鮮なトマトの数と腐ったトマトの位置を記録
    for(let i = 0; i < arr.length; i++){
        for(let j = 0; j < arr[i].length; j++){
            if(arr[i][j] === 1){
                fresh += 1;
            };
            if(arr[i][j] === 2){
                curr.push([i, j]);
            };
        };
    };
    // 新鮮なトマトが最初から存在しない場合は 0 を返す
    if(!fresh){
        return 0;
    };
    // 多始点BFS：1分ごとに腐敗を広げる
    while(curr.length > 0){
        count += 1;
        const next = [];
        const rotten = (i, j) => {
            arr[i][j] = 2
            next.push([i, j])
            fresh -= 1
        };
        for(const [i, j] of curr){
            if (arr[i - 1] && arr[i - 1][j] === 1) {
                rotten(i - 1, j);
            };
            if (arr[i + 1] && arr[i + 1][j] === 1) {
                rotten(i + 1, j);
            };
            if (arr[i][j - 1] === 1) {
                rotten(i, j - 1);
            };
            if (arr[i][j + 1] === 1) {
                rotten(i, j + 1);
            };
        }
        curr = next
    };
    // すべて腐ったなら経過分数、届かなかったトマトがあれば -1
    return fresh === 0 ? count : -1;
};
console.log(timeToRot(arr));

アルゴリズムのポイント

• 初回の走査で、新鮮なトマトの総数（fresh）と腐ったトマトの初期座標（curr）をまとめて収集します。
• curr をキューとして扱い、「現在腐っているトマト」を1分単位で一括処理します。これはいわゆる多始点BFSの手法です。
• 上下左右の4方向をチェックし、隣接する新鮮なトマトがあれば腐らせて、次の世代のキュー（next）に追加します。
• ループ終了後、fresh が 0 になっていれば経過分数（count）を返し、空きセルなどで隔離されて腐らなかったトマトが残っていれば -1 を返します。

計算量はグリッドのサイズを M×N とした場合 O(M×N) に収まるため、大きな入力に対しても非常に効率的に動作します。

出力結果

コンソールには次のように表示されます。

4