Pythonで3D図形の表面積を求める方法【アルゴリズム解説付き】

問題の概要

N×M の行列 A が与えられ、これは3D図形を表しています。点 (i, j) における柱の高さは A[i][j] であり、この図形全体の表面積を求めるのが目的です。

たとえば、入力が N = 3、M = 3、A = [[1, 4, 5], [3, 3, 4], [1, 3, 5]] の場合、出力は 72 となります。

解法のアプローチ

この問題は、各セルと隣接セルの「高さの差」に注目することで効率的に解けます。表面積は大きく分けて2つの要素で構成されます。

• 上面と底面： グリッドの各マスには必ず上面と底面が存在するため、合計で N × M × 2 となります。
• 側面： 隣接するセル同士の高さの差が、そのまま見える側面の面積になります。さらに、図形の端（最下段・最右列）は外側に面する側面を持つため、その分も加算します。

アルゴリズムの手順

1. 結果を格納する変数 res を 0 で初期化します。
2. i を 0 から N-1 まで、j を 0 から M-1 まで二重ループで回します。
3. up_side（上方向の隣接セルの高さ）と left_side（左方向の隣接セルの高さ）を 0 で初期化します。
4. i > 0 の場合は up_side を array[i-1][j] に、j > 0 の場合は left_side を array[i][j-1] に設定します。
5. |array[i][j] − up_side| + |array[i][j] − left_side| を res に加算します。
6. i が N−1（最下段）の場合と、j が M−1（最右列）の場合は、それぞれ array[i][j] を res に加算します。
7. ループ終了後、res に N × M × 2 を加算して返します。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

M = 3
N = 3

def get_surface_area(array):
    res = 0
    for i in range(N):
        for j in range(M):
            up_side = 0
            left_side = 0
            if (i > 0):
                up_side = array[i - 1][j]
            if (j > 0):
                left_side = array[i][j - 1]
            res += abs(array[i][j] - up_side) + abs(array[i][j] - left_side)
            if (i == N - 1):
                res += array[i][j]
            if (j == M - 1):
                res += array[i][j]
    res += N * M * 2
    return res

array = [[1, 4, 5], [3, 3, 4], [1, 3, 5]]
print(get_surface_area(array))

入力

[[1, 4, 5], [3, 3, 4], [1, 3, 5]]

出力

72

まとめ

このアルゴリズムの計算量は O(N × M) で、グリッドの全セルを一度走査するだけで表面積を求められます。隣接セルとの高さ差を累積的に足し合わせ、最後に上下の面を一括で加算するというシンプルな発想がポイントです。競技プログラミングでも頻出のパターンなので、ぜひ覚えておきましょう。