Pythonで各建物の高さをスカイラインを維持したまま最大まで増加させる行列を求めるプログラム

問題の概要

2次元の行列を考えてみましょう。ここで matrix[r][c] は、都市にあるマンション（建物）の高さを表します。東西方向のスカイラインは行列の各行の最大値を取ることで得られ、南北方向のスカイラインは各列の最大値を取ることで得られます。

この記事のゴールは、東西・南北どちらのスカイラインも一切変えずに、各建物の高さを可能な限り最大まで引き上げた新しい行列を作ることです。

入力例

出力例

この場合、東西方向のスカイラインは [4, 7, 10]、南北方向のスカイラインは [8, 9, 10] です。1行目のすべての値を4に、2行目のすべての値を7に引き上げても、スカイラインは変化しません。これが「可能な限り高さを増やす」という意味です。

解法のアプローチ

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

• r := 行列の各行の最大値からなるリスト

• c := 行列の各列の最大値からなるリスト

• i を 0 から行数まで繰り返す

  • j を 0 から列数まで繰り返す

    • r[i] < c[j] の場合：
      matrix[i][j] := r[i]

    • それ以外の場合：
      matrix[i][j] := c[j]

• matrix を返す

ポイントは、各セルに対して「その行の最大値」と「その列の最大値」のうち小さい方を設定することです。そうすることで、各行・各列の最大値（つまりスカイライン）が変わらない範囲で、各セルを理論上の上限まで高くできます。

Pythonでの実装例

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

class Solution:
    def solve(self, matrix):
        r = [max(i) for i in matrix]
        c = [max(i) for i in zip(*matrix)]
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if r[i] < c[j]:
                    matrix[i][j] = r[i]
                else:
                    matrix[i][j] = c[j]
        return matrix

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

入力

[[2, 3, 4],
[5, 6, 7],
[8, 9, 10]]

出力

[[4, 4, 4], [7, 7, 7], [8, 9, 10]]

この実装では、zip(*matrix) を使うことで行列を転置し、各列の最大値を簡単に取得しています。計算量は O(R×C)（Rは行数、Cは列数）となり、非常に効率的です。