Pythonで各行を反転しても行列が変わらないかどうかを判定する方法

問題の概要

正方行列が与えられたとき、各行を反転（リバース）した後も、行列全体が元のまま変わらないかどうかを判定するプログラムをPythonで作成してみましょう。

言い換えると、この問題は「すべての行が回文（左右対称）になっているか」を確認する問題です。ある行を反転しても元の並びと同じになるなら、その行は回文であると言えます。

たとえば、次のような行列が入力された場合を考えてみます。

この場合、出力は True になります。どの行も反転しても元の並びとまったく同じになるためです。

解法のアプローチ

この問題は、両ポインタ（two pointers）テクニックを使うことでシンプルかつ効率的に解くことができます。手順は以下の通りです。

• n := 行列の行数とする
• i を 0 から n - 1 まで繰り返す
  • left := 0、right := n - 1 と初期化する
  • left <= right の間、以下を繰り返す
    • matrix[i][left] と matrix[i][right] が等しくない場合は False を返す
    • left を +1、right を -1 して中央に向かって進める
• すべての行で対称性が確認できたら True を返す

つまり、各行の左端と右端から順に要素を比較していき、対応する位置の値がひとつでも異なれば、その行は反転すると変化してしまうため False を返します。

Pythonでの実装例

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

def solve(matrix):
    n = len(matrix)
    for i in range(n):
        left = 0
        right = n - 1
        while left <= right:
            if matrix[i][left] != matrix[i][right]:
                return False
            left += 1
            right -= 1
    return True

matrix = [
        [6,8,6],
        [2,8,2],
        [3,3,3]]
print(solve(matrix))

入力

[
    [6,8,6],
    [2,8,2],
    [3,3,3]]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n²) です。n 行それぞれに対して、最大で n/2 回の比較を行うためです。また、追加のデータ構造を使用しないため、空間計算量は O(1) となり、メモリ面でも非常に効率的です。