Pythonで3D形状の表面積を計算する方法

問題の概要

N×Nのグリッドを用意し、その中に1×1×1の立方体をいくつか配置することを考えます。grid[i][j] の値 v は、セル (i, j) の上に v 個の立方体が積み重なった「塔」が存在することを表します。このとき、全体としてできあがる3D形状の総表面積を求めるのが目的です。

たとえば、入力が [[1,2],[3,4]] の場合、出力は 34 になります。

解法のアプローチ

表面積は、次の3つの要素に分解して考えると整理しやすくなります。

• 上下の面(z方向):立方体が1つでも置かれているセルには、必ず上面と底面が1つずつ現れます。したがって、この成分は「非ゼロのセル数 × 2」となります。
• 側面(x・y方向):各塔の高さを v とすると、周囲に何もない場合の側面積は 4×v です。まず全セルの値の合計 × 4 を基本値とします。
• 隣接による隠れ:高さ a と b の塔が隣り合うと、接触部分の面 min(a, b) ずつが互いに見えなくなります。そのため、2×min(a, b) を差し引く必要があります。これを行方向と列方向の両方について計算します。

最終的な表面積は、次の式で求められます。

表面積 = 上下の面 + (側面の合計 − 行方向の隠れ − 列方向の隠れ)

手順の詳細

まず、隣接する2つの高さから生じる隠れ面積を返す関数 adjacentArea() を定義します。

1. area を 0 で初期化します。
2. i を 0 から行の長さ − 2 まで繰り返します。
3. row[i] と row[i+1] がどちらも非ゼロであれば、area += 2 * min(row[i], row[i+1]) を実行します。
4. area を返します。

続いて、メイン処理では以下を計算します。

• z = 非ゼロセルの総数 × 2(上面と底面の分)
• x_plus_y = グリッド全要素の合計 × 4(すべての側面の分)
• x_adjacent = 各行に対する adjacentArea() の合計
• y_adjacent = 各列(zip(*grid) で転置)に対する adjacentArea() の合計
• 戻り値 = z + (x_plus_y - x_adjacent - y_adjacent)

Pythonでの実装例

class Solution:
    def surfaceArea(self, grid):
        def adjacentArea(row):
            area = 0
            for i in range(len(row) - 1):
                if row[i] and row[i + 1]:
                    area += 2 * min(row[i], row[i + 1])
            return area

        z = sum(sum(i > 0 for i in row) for row in grid) * 2
        x_plus_y = sum(sum(row) for row in grid) * 4
        x_adjacent = sum(adjacentArea(row) for row in grid)
        y_adjacent = sum(adjacentArea(row) for row in zip(*grid))
        return z + (x_plus_y - x_adjacent - y_adjacent)

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

入力

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

出力

34

計算の内訳

この結果がどのように導かれるのか、具体的な数値で確認してみましょう。

• z = 非ゼロセルが4つなので 4 × 2 = 8
• x_plus_y = 合計値が 1+2+3+4 = 10 なので 10 × 4 = 40
• x_adjacent(行方向)= 2×min(1,2) + 2×min(3,4) = 2 + 6 = 8
• y_adjacent(列方向)= 2×min(1,3) + 2×min(2,4) = 2 + 4 = 6

よって、表面積 = 8 + (40 − 8 − 6) = 34 となります。

計算量

グリッドの各セルを定数回走査するだけなので、時間計算量は O(N²)、追加の空間計算量は O(1) です。グリッドサイズが大きくなっても効率的に動作するアプローチといえます。