JavaScriptで解くゾンビ黙示録：感染区域を特定するフラッドフィルのケーススタディ

デジタル都市で恐ろしいゾンビウイルスが猛威を振るっています。私たちはデジタルCDC（疾病対策センター）に勤め、都市の地図を監視しながらウイルスに汚染された区域を特定するのが任務です。この情報をもとに、デジタル軍はどこへ爆撃を仕掛けるべきかを判断します。

今回の敵は新型のデジタルゾンビ。縦・横方向にしか移動できず、しかも自分と同じ数値のセルにしか感染しないという特異な性質を持っています。

問題の概要

入力として、数値が並んだ二次元配列（マトリックス）が渡されます。

なぜかは分かりませんが、最初の感染者（ペイシェントゼロ）は必ず都市の北西エリア、すなわちマトリックスの [0][0] 要素で発見され、感染はそこから上下左右への移動を通じて周囲のセルへと広がっていきます。

求められているのは、汚染区域をすべて「1」、無事な区域を「0」としてマークしたマップ（二次元配列）を返す関数です。

言い換えると、「[0][0] と同じ値を持ち、[0][0] から上下左右の移動だけで到達できるセル（途中に別の値のセルを挟まないもの）」をすべて見つけ出す必要があります。これは画像処理などでもおなじみのフラッドフィル（Flood Fill）アルゴリズムの典型例といえます。

サンプルコード

実際の実装例がこちらです。

const arr = [
    [9, 1, 2, 3, 4, 1, 2, 9],
    [9, 9, 9, 2, 1, 5, 9, 9],
    [9, 2, 9, 3, 7, 9, 1, 9],
    [6, 9, 9, 9, 0, 9, 2, 9],
    [5, 4, 3, 9, 9, 9, 4, 9],
    [9, 3, 9, 5, 8, 9, 9, 9],
    [9, 9, 9, 9, 9, 9, 7, 9],
    [9, 9, 1, 2, 3, 9, 8, 9]
];
const findZombies = arr => {
    let i, j, result = [],
    zombie = arr[0][0],
    tree = {};
    const chance = ([i, j]) => {
        if (!tree[i] || !tree[i][j]) return;
        result[i][j] = 1;
        var temp = tree[i][j];
        tree[i][j] = undefined;
        temp.forEach(chance);
    }
    for (i = 0; i < arr.length; i++) {
        result.push([]);
        for (j = 0; j < arr[i].length; j++) {
            result[i].push(0);
            if (arr[i][j] !== zombie) continue;
            if (!tree[i]) tree[i] = {};
            tree[i][j] = [[i, j - 1], [i, j + 1], [i - 1, j], [i + 1, j]].filter(([x, y]) => arr[x] && arr[x][y] === zombie);
        };
    };
    chance([0, 0]);
    return result;
};
console.log(findZombies(arr));

このコードを実行すると、コンソールには次の結果が出力されます。

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

コードの解説

処理の流れを順番に見ていきましょう。

① 隣接グラフの構築

まず二重ループで全セルを走査し、arr[0][0] と同じ値を持つセルについて、上下左右に隣接する同値セルの座標リストを tree オブジェクトに登録します。これにより「感染が広がりうる経路」の全体像がグラフとして表現されます。

② 再帰による感染拡大

chance 関数は、指定されたセルを起点に再帰的に呼び出され、到達可能なセルを一つずつ訪れます。訪問済みセルは tree[i][j] を undefined で上書きすることで再訪を防止し、result 配列の該当位置を 1 に更新していきます。

③ 汚染マップの完成

chance([0, 0]) の実行が終わると、result 配列には [0][0] から連結している同値セルだけが 1 として記録され、それ以外は初期値の 0 のまま残ります。これこそが、爆撃目標を示す「汚染マップ」です。

このアルゴリズムの計算量は O(n × m)（n・m はマトリックスの行数・列数）で、各セルを高々一度ずつ訪れるため非常に効率的です。同様の問題は DFS（深さ優先探索）や BFS（幅優先探索）、Union-Find などを用いても解くことができます。