Pythonで全員が集まるための最小ステップ数を求めるプログラム(BFS活用)

問題の概要

2次元グリッド(マトリックス)が与えられ、各セルには次のいずれかの値が格納されています。0は空きセル、1は壁、2は人を表します。人は上下左右の4方向へ移動するか、その場にとどまるかを選択でき、いずれも1時間単位を消費します。ここで、全員が集まるまでにかかる時間を最小化できる「移動可能なセル」を見つけ、その時間(必要な最小ステップ数)を返すことが目的です。

なお、複数の人が同じ空きセルを通過することは許され、任意の2人の間には必ず何らかの経路が存在すると仮定して構いません。

入力例

この場合の出力は 2 となります。すべての人が matrix[1, 1] の位置に最大2ステップで集まることができるためです。

解決のためのアルゴリズム

この問題は、各人を起点として幅優先探索(BFS)で全セルへの距離を求め、全員が到達可能なセルの中で「最大距離」が最小となるものを選ぶことで解けます。集合にかかる時間は、その地点から最も遠い人のステップ数で決まるためです。

BFS関数の手順

1. bfs(r, c) 関数を定義します。始点 (r, c) をキューに挿入し、dist マップを {(r, c): 0} で初期化します。
2. キューからセルを取り出し、その距離(dist値)が15を超えていたら探索を打ち切ります(探索深度の制限)。
3. 上下左右の隣接セル (nr, nc) のうち、壁ではなく未訪問のものに対して dist[nr, nc] = dist[r, c] + 1 を設定し、キューの末尾に追加します。
4. 探索完了後、dist を返します。

メイン処理の手順

1. dist を None で初期化します。
2. グリッドを走査し、値が 2(人)であるセルごとに bfs(r, c) を実行して ndist を取得します。
3. 最初の人であれば dist = ndist とし、2人目以降は既存の dist の各キーについて次のように処理します。
   • ndist にも同じキーが存在する場合：dist[key] = max(dist[key], ndist[key]) と更新します(全員が揃う時間は最も遠い人に合わせるため)。
   • ndist にキーが存在しない場合：そのセルを dist から削除します(誰かが到達できないため集合候補から除外)。
4. 最後に、dist が空でなければその値の最小値を返し、空であれば 0 を返します。

なお、隣接セルの判定に使われている A[nr][nc] & 1 == 0 はビット演算によるテクニックです。壁は 1(奇数)、空きセルは 0・人は 2(偶数)なので、この条件で壁だけを効率的に除外できます。

実装例(Python)

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])

      def get_neighbor(r, c):
         for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
            if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
               yield nr, nc

      def bfs(r, c):
         queue = [(r, c)]
         dist = {(r, c): 0}
         for r, c in queue:
            if dist[r, c] > 15:
               break
            for nr, nc in get_neighbor(r, c):
               if (nr, nc) not in dist:
                  dist[nr, nc] = dist[r, c] + 1
                  queue.append((nr, nc))
         return dist

      dist = None
      for r, row in enumerate(A):
         for c, val in enumerate(row):
            if val == 2:
               ndist = bfs(r, c)
               if dist is None:
                  dist = ndist
               else:
                  for key in list(dist.keys()):
                     if key in ndist:
                        dist[key] = max(dist[key], ndist[key])
                     else:
                        del dist[key]
      return min(dist.values()) if dist else 0

ob = Solution()
matrix = [
   [2, 0, 1, 0],
   [1, 0, 0, 2],
   [2, 0, 2, 0]
]
print(ob.solve(matrix))

入力

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

出力

2

計算量について

人数を P、グリッドのサイズを R×C とすると、各人について BFS を1回実行するため、時間計算量は O(P × R × C) となります。人数やグリッドが大きくなっても線形オーダーで処理できる、効率的なアプローチです。