Pythonで行列上のZ字形を形成する要素の合計を求める方法

n × n の行列 M が与えられたとき、その中で「Z」の字形を形成するすべての要素の合計を求めます。ここでいうZ字は、最初の行全体、最後の行全体、そして右上から左下へ向かう副対角線によって構成されます。

たとえば、入力として次のような行列が与えられたとします。

この場合の出力は 23 になります。Z字を構成する要素は [4+3+2+1+2+5+6] となり、その合計が 23 だからです。

解き方のアプローチ

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

• 変数 n に行列の行数を代入します。
• n が 2 以下の場合、Z字の形が成立しないため、行列内の全要素の合計をそのまま返します。
• first_row に最初の行の要素の合計を代入します。
• last_row に最後の行の要素の合計を代入します。
• diagonal に、i を 1 から n-2 の範囲で動かしたときの matrix[i][n-1-i](副対角線の中央部分)の合計を代入します。
• first_row + last_row + diagonal を結果として返します。

なお、副対角線の両端(matrix[0][n-1] と matrix[n-1][0])はそれぞれ最初の行・最後の行に含まれるため、二重にカウントしないよう範囲を 1 から n-2 に限定しています。このアルゴリズムの計算量は O(n) であり、行列のサイズに対して非常に効率的に処理できます。

実装例

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        if n <= 2:
            return sum(sum(row) for row in matrix)
        first_row = sum(matrix[0])
        last_row = sum(matrix[n-1])
        diagonal = sum(matrix[i][n-1-i] for i in range(1, n-1))
        return first_row + last_row + diagonal

ob = Solution()
matrix = [
    [4, 3, 2],
    [9, 1, 8],
    [2, 5, 6]
]
print(ob.solve(matrix))

入力

matrix = [[4, 3, 2],
[9, 1, 8],
[2, 5, 6]]

出力

23