Pythonでマトリクスの全セルを同じ色に揃えるための最小操作回数を求めるプログラム

2次元マトリクスMが与えられます。各セルには色を表す値が格納されており、上下左右に隣接する同色のセル同士はひとつのグループとして扱われます。ここで、「ひとつのグループに含まれるすべてのセルを任意の色に塗り替える」という操作を考えます。すべてのセルを同じ色に揃えるために必要な最小の操作回数を求めるのが本記事のテーマです。ただし、一度色を変えたセルは、それ以降二度と変更できないという制約があります。

入力例と出力

例として、次のようなマトリクスを考えてみましょう。

この場合の出力は2となります。たとえば、下段左端の「2」のセルを色1で塗り、続いて下段の「3」を色1で塗ることで、わずか2回の操作ですべてのセルを色1に揃えられるからです。

解法のアプローチ

この問題は、深さ優先探索（DFS）を使って「色ごとのグループ（連結成分）の数」を数えることで効率的に解けます。ポイントは以下のとおりです。

• 最終的な色以外の各グループは、それぞれ1回の操作で塗り替えられる
• したがって答えは「グループの総数 − 最終色に選んだ色のグループ数」で求まる
• 操作回数を最小化するには、グループ数が最も多い色を最終色として選べばよい

手順の詳細

1. マトリクスが空の場合は0を返す。
2. dfs() 関数を定義する。引数は i, j, matrix, val。インデックスが範囲外の場合や、すでに訪問済み（値が-1）のセルは即座にreturnする。
3. セルの値が指定された色valと一致していれば、そのセルを-1でマークし、上下左右の4方向へ再帰的に探索を進める。一致しなければ何もせずreturnする。
4. メイン処理では、すべてのセルを走査し、未訪問のセルを見つけるごとに辞書dでその色のカウントを+1し、dfs()を呼び出して同じグループ全体をマークする。
5. こうしてdには「色ごとのグループ数」が記録される。
6. dを値でソートし、グループ数が最大の色をsafe（最終色）として採用する。
7. safe以外の色のグループ数を合計したものが答えとなる。

Pythonでの実装例

それでは、実際のコードを見ていきましょう。

from collections import defaultdict

class Solution:
   def solve(self, matrix):
      if not matrix:
         return 0

      def dfs(i, j, matrix, val):
         n, m = len(matrix), len(matrix[0])
         if i < 0 or i > n - 1 or j < 0 or j > m - 1:
            return
         if matrix[i][j] == -1:
            return
         if matrix[i][j] == val:
            matrix[i][j] = -1
            dfs(i, j + 1, matrix, val)
            dfs(i + 1, j, matrix, val)
            dfs(i, j - 1, matrix, val)
            dfs(i - 1, j, matrix, val)
         else:
            return

      n, m = len(matrix), len(matrix[0])
      d = defaultdict(int)
      for i in range(n):
         for j in range(m):
            val = matrix[i][j]
            if val != -1:
               d[val] += 1
               dfs(i, j, matrix, val)

      l = sorted(d, key=lambda x: d[x])
      safe = l[-1]
      res = 0
      for k, v in d.items():
         if k != safe:
            res += v
      return res

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

入力

matrix = [[2, 2, 2, 2],[1, 1, 1, 1],[2, 3, 2, 1]]

出力

2

計算量について

時間計算量・空間計算量はいずれもO(n×m)です。nとmはそれぞれマトリクスの行数・列数に相当します。各セルはDFSによって一度だけ訪問されるため、行列のサイズに比例した計算量で処理が完了します。