Pythonで二値行列の基準を満たす要素の個数を求めるプログラム

0と1だけで構成される二値行列が与えられたとき、次のルールを満たす要素の個数を求める問題を考えてみましょう。

• matrix[r, c] = 1 である

• r行目の他のすべての列 j（j ≠ c）について matrix[r, j] = 0 であり、かつ c列目の他のすべての行 i（i ≠ r）について matrix[i, c] = 0 である

簡単に言えば、「そのセルが1であり、同じ行にも同じ列にも他の1が存在しない」ようなセルの数を数えるというものです。

たとえば、次のような入力を考えます。

この場合の出力は 3 になります。条件を満たしているのはセル (0,2)、(1,0)、(2,1) の3つだからです。それぞれのセルを見ると、同じ行・同じ列に他の1がないことが確認できます。

解き方のアプローチ

この問題は、各行・各列の合計値をあらかじめ計算しておくことで効率的に解けます。あるセルが条件を満たすのは「その行の合計が1」かつ「その列の合計が1」の場合だけだからです。以下の手順で進めます。

• 行列が空であれば、0 を返す

• row := 各行の要素の合計を格納したリスト

• col := 各列の要素の合計を格納したリスト

• m := 行数、n := 列数

• res := 0（答えを格納する変数）

• すべてのセル (r, c) について、matrix[r][c] == 1 かつ row[r] == 1 かつ col[c] == 1 であれば res を +1 する

• res を返す

この方法なら、条件判定のたびに行や列を走査し直す必要がなく、全体の時間計算量は O(m × n) に抑えられます。

実装例

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

def solve(matrix):
    if not matrix:
        return 0

    row = [sum(r) for r in matrix]
    col = [sum(c) for c in zip(*matrix)]

    m, n = len(matrix), len(matrix[0])
    res = 0
    for r in range(m):
        for c in range(n):
            if matrix[r][c] == 1 and row[r] == 1 and col[c] == 1:
                res += 1
    return res

matrix = [
   [0, 0, 1],
   [1, 0, 0],
   [0, 1, 0]
]
print(solve(matrix))

ここでのポイントは zip(*matrix) の部分です。これは行列を転置して列ごとにまとめるテクニックで、各列の合計を簡潔に計算できます。

入力

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

出力

3

このように、行と列の合計を前計算しておくことで、シンプルかつ高速に条件を満たすセルを数えられるのがこのアルゴリズムの魅力です。