3D形状の投影面積の合計を求めるアルゴリズム(Python実装例)

問題の概要

N × N のグリッドが与えられ、そこに x・y・z 軸に平行な 1 × 1 × 1 の立方体を配置することを考えます。グリッドの各要素 v = grid[i][j] は、セル (i, j) の上に v 個の立方体を縦に積み重ねた「塔」を表しています。

この立体を、上面(xy平面)、正面(yz平面)、側面(zx平面)の3方向から見たときの投影面積をそれぞれ求め、その合計を計算するのがこの問題の目的です。

入力例と出力例

たとえば、入力が [[1,2],[3,4]] の場合を考えてみましょう。

この場合、出力は 17 となります。

解法のアプローチ

3つの投影面積は、それぞれ次のようにして求められます。

• xy平面(上面図):立方体が1つでも置かれているセル(値が0より大きいセル)の個数を数えます。
• yz平面(正面図):各行における最大の高さを合計します。行の中で最も高い塔が、その行全体の影の範囲を決めるためです。
• xz平面(側面図):各列における最大の高さを合計します。

これらを踏まえると、アルゴリズムは以下の手順で進められます。

1. 変数 xy、yz、xz をすべて 0 で初期化します。
2. グリッドの各行 r について、その行の最大値を yz に加算します。
3. 同時に、行内の各セル grid[r][c] を調べ、値が 0 より大きければ xy を 1 ずつ増やします。
4. グリッドの各列について、その列の最大値を xz に加算します。
5. 最後に xy + yz + xz を返します。

Pythonによる実装例

class Solution(object):
    def projectionArea(self, grid):
        xy = 0
        yz = 0
        xz = 0
        for r, row in enumerate(grid):
            yz += max(row)
            for c, col in enumerate(row):
                if grid[r][c] > 0:
                    xy += 1
        for col in zip(*grid):
            xz += max(col)
        return xy + yz + xz

ob = Solution()
print(ob.projectionArea([[1,2],[3,4]]))

入力

[[1,2],[3,4]]

出力

17

コードの解説

この実装では、最初のループで上面図(xy)と正面図(yz)の面積を同時に求めています。max(row) によってその行で最も高い塔の高さを取得して yz に加算しながら、値が 0 より大きいセルをカウントして xy を更新していきます。

続いて、zip(*grid) を使ってグリッドを転置し、各列の最大値を xz に加算することで、側面図(xz)の面積を求めます。

入力 [[1,2],[3,4]] の場合、xy = 4(すべてのセルに立方体が存在)、yz = 2 + 4 = 6、xz = 3 + 4 = 7 となり、合計は 4 + 6 + 7 = 17 です。

計算量は、グリッドのサイズを N × N とすると時間計算量 O(N²)、空間計算量 O(1) で、非常に効率的な解法といえます。