Pythonで左上と右下のセルを分断するために必要な最小の壁の数を求めるプログラム

2次元のバイナリ行列を考えます。「0」は空きセル、「1」は壁を表します。この問題では、左上のセルから右下のセルへ至る経路が完全に存在しなくなるようにするために、最低何個のセルを壁へ変更すればよいかを求めます。ただし、左上と右下のセルそのものに壁を設置することはできません。また、移動は上下左右の4方向のみが許され、斜め移動はできません。

例として、次のような入力を考えてみましょう。

この場合の出力は「2」です。たとえば下のように2つのセルを壁に変えることで、左上から右下へのすべての経路を遮断できます。

解法のアプローチ

この問題は、グラフ理論における関節点（Articulation Point）の概念を利用して解きます。マス目をグラフの頂点、隣り合う空きセル同士を結ぶ辺とみなし、DFS（深さ優先探索）によって関節点を検出します。全体の手順は以下の通りです。

• R を行列の行数、C を列数とします。
• visited（訪問済み頂点の集合）、tin と low（DFS用のタイムスタンプを記録する辞書）、timer（カウンタ）、bridge_pts（関節点を格納する集合）、par（親頂点を記録する辞書）を初期化します。
• src を (0, 0)、tgt を (R−1, C−1) とします。
• 関数 dfs(v, parent) を定義します。
  • v を訪問済みにし、par[v]、tin[v]、low[v] を設定して timer を1進めます。
  • v の各近傍 to に対して、to が親と同じならスキップします。すでに訪問済みなら low[v] を tin[to] との最小値で更新し、未訪問なら再帰的に dfs(to, v) を呼び出して low[v] を low[to] との最小値で更新します。
  • low[to] >= tin[v] かつ parent が存在する場合、v を bridge_pts に追加します。これは「子の部分木から親以上の頂点へ戻れない」ことを意味し、v が関節点であることを示します。
  • parent が null で子の数が2以上の場合も、v を bridge_pts に追加します（探索の根が関節点になるケースです）。
• 関数 bfs(root) を定義します。両端キュー（deque）を用いて探索を行い、tgt に到達できれば True、できなければ False を返します。
• メイン処理は次の通りです。
  • dfs(src, None) を実行します。
  • tgt が par に存在しない場合、始点から終点まで最初から経路がないため 0 を返します。
  • bridge_pts に含まれる各セル (i, j) を壁（1）に変更します。
  • bfs(src) が True を返す（まだ経路が残っている）場合は 2 を返し、そうでなければ 1 を返します。

注目すべきは、答えが最大でも2であるという点です。左上と右下をつなぐ任意の単純パス上のセルを順に壁にしていけば、遅くとも2個で必ず経路を遮断できるためです。関節点をすべて壁にした時点で経路が残っていなければ1、残っていれば2、そもそも経路がなければ0、という判定ロジックになっています。

Pythonでの実装例

それでは、理解を深めるために実際の実装を見てみましょう。

from collections import deque


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

      def get_neighbors(i, j):
         for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == 0:
               yield ii, jj

      visited = set()
      tin = {}
      low = {}
      timer = 0
      bridge_pts = set()
      par = {}
      src = (0, 0)
      tgt = (R - 1, C - 1)

      def dfs(v, parent):
         nonlocal timer
         visited.add(v)
         par[v] = parent
         tin[v] = timer
         low[v] = timer
         timer += 1
         children = 0
         for to in get_neighbors(*v):
            if to == parent:
               continue
            if to in visited:
               low[v] = min(low[v], tin[to])
            else:
               dfs(to, v)
               low[v] = min(low[v], low[to])
               if low[to] >= tin[v] and parent is not None:
                  bridge_pts.add(v)
               children += 1
         if parent is None and children > 1:
            bridge_pts.add(v)

      def bfs(root):
         Q = deque([root])
         visited = set([root])
         while Q:
            v = Q.pop()
            if v == tgt:
               return True
            for w in get_neighbors(*v):
               if w not in visited:
                  visited.add(w)
                  Q.appendleft(w)
         return False

      dfs(src, None)
      if tgt not in par:
         return 0
      for i, j in bridge_pts:
         matrix[i][j] = 1
      if bfs(src):
         return 2
      return 1


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

入力

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

出力

2