JavaScriptで迷路の終点への経路を見つける方法

問題

N×N の正方行列で表される迷路が与えられます。壁は 'W'、通行可能な空きマスは '_' で表され、移動は上下左右の4方向がいつでも可能です。

この迷路の左上 [0, 0] からスタートし、右下の終点 [N - 1, N - 1] にたどり着けるかどうかを判定する JavaScript 関数を作成します。到達できる場合は true、できない場合は false を返します。

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

迷路のような「到達可能性」を求める問題には、幅優先探索（BFS）が適しています。キューを使って探索対象のマスを順番に処理しながら、訪問済みのマスを別の文字（ここでは '#'）で上書きすることで、同じマスを二度探索しないようにします。

具体的な流れは以下のとおりです。

• スタート地点 [0, 0] をキューに入れる。
• キューが空になるまで、先頭の座標を取り出しては上下左右の隣接マスを確認する。
• 隣接マスが迷路の範囲内かつ空きマス（'_'）であれば、訪問済みを示す '#' に書き換えてキューに追加する。
• 探索終了後、終点 [N - 1, N - 1] が '#' になっていれば到達可能と判定する。

コード例

const maze = [
  ['_', 'W', 'W', 'W'],
  ['_', 'W', 'W', 'W'],
  ['W', '_', '_', 'W'],
  ['W', 'W', 'W', '_']
];

const canFindPath = (m = []) => {
  const h = m.length;     // 迷路の高さ（行数）
  const w = m[0].length;  // 迷路の幅（列数）
  const queue = [[0, 0]]; // 探索待ちの座標を管理するキュー

  while (queue.length) {
    const [x, y] = queue.shift();

    // 壁や訪問済みのマスはスキップ
    if (m[y][x] !== '_') continue;

    // 訪問済みとしてマーク
    m[y][x] = '#';

    // 上下左右の4方向を確認
    for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nx = x + dx;
      const ny = y + dy;
      if (
        nx >= 0 && nx < w &&
        ny >= 0 && ny < h &&
        m[ny][nx] === '_'
      ) {
        queue.push([nx, ny]);
      }
    }
  }

  // 終点が訪問済みなら到達可能
  return m[h - 1][w - 1] === '#';
};

console.log(canFindPath(maze));

出力結果

true

コードのポイント

• 座標の管理： 行列へのアクセスは m[y][x] のように「行・列」の順で行うため、キューには [x, y]（列, 行）の形式で座標を格納しています。
• 訪問管理： visited 配列を別途用意せず、元の行列自体を '#' で書き換えることでメモリを節約できます。元のデータを保持したい場合は、関数に渡す前にコピーしましょう。
• 境界チェック： nx・ny が迷路の範囲内にあるかを必ず確認し、配列外参照を防いでいます。
• 判定条件： 終点が '#' に置き換わっていれば、そこへ至る経路が存在したことを意味します。

なお、元のコードでは空きマスの記号（'_'）と判定条件の記号（'.'）が一致しておらず、意図したとおりに動作しないケースがありました。本記事のコードではこの不整合を修正し、正しく動作するようになっています。

計算量

各マスは最大1回ずつ訪問されるため、時間計算量は O(N²)、キューと訪問マーク分の空間計算量も O(N²) です。迷路のサイズが大きくなっても線形に近い効率で処理できます。