Pythonで行列の各行を反転し、ビットを反転させる方法

本記事では、2値行列（0と1のみで構成される行列）を扱うアルゴリズム問題をPythonで解く方法を解説します。具体的には、行列の各行を左右に反転（リバース）した後、各ビットを反転（0を1に、1を0に変換）する処理を実装します。

問題の概要

2値行列 mat が与えられたとします。まず行列内の各行を選択して行を逆順に並べ替え、その後、行内の各要素について0と1を入れ替えます。

例えば、次のような入力が与えられた場合を考えてみましょう。

この場合、出力は以下のようになります。

解法のアプローチ

この問題は、以下の手順で解決できます。

• 行インデックスを表す変数 track を 0 で初期化する。
• 行列 mat の各行に対して、以下の処理を繰り返す。
  • まず、その行を reverse() メソッドで逆順にする。
  • 列インデックスを表す変数 tracker を 0 で初期化する。
  • 行内の各値 val に対して、以下の処理を行う。
    • val が 1 の場合は mat[track][tracker] を 0 に設定する。
    • それ以外の場合は mat[track][tracker] を 1 に設定する。
    • tracker を 1 増やす。
  • 1行の処理が終わったら track を 1 増やす。
• すべての行の処理が完了したら、更新された行列 mat を返す。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, mat):
        track = 0
        for row in mat:
            row.reverse()
            tracker = 0
            for val in row:
                if val == 1:
                    mat[track][tracker] = 0
                else:
                    mat[track][tracker] = 1
                tracker += 1
            track += 1
        return mat

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

入力

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

出力

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

コードのポイント

この実装では、Pythonのリストが参照渡しであることを利用しています。for row in mat で取得した row に対して row.reverse() を呼び出すと、元の行列 mat 内の該当行も直接書き換えられます。そのため、反転後の行の値を読みながら、同じ位置の mat[track][tracker] にビット反転した結果を上書きしても、処理に矛盾は生じません。

なお、より簡潔に書きたい場合は、スライス記法とリスト内包表記を組み合わせて、次のように1行で表現することも可能です。

def solve(mat):
    return [[1 - v for v in row[::-1]] for row in mat]

row[::-1] で行を逆順にし、1 - v で0と1を反転させています。どちらの方法でも計算量は O(n×m)（nは行数、mは列数）となり、効率的に処理できます。