Pythonで島（図形）の周囲長を求めるアルゴリズムと実装方法

問題の概要

0が空きセル、1がブロック（図形の一部）を表す2値行列を考えます。このとき、図形の周囲長（外周の長さ）を求めるのが課題です。なお、図形の内部に穴は存在しないものとします。

例えば、次のような入力が与えられた場合を考えてみましょう。

この場合の出力は 14 になります。

解法のアプローチ

基本的な考え方はシンプルです。各セルは最大で4つの辺を外周に持ちますが、隣接するセルも1である場合、その共有される辺は外周に含まれません。そこで、以下の手順で計算を行います。

• d := 0（現在の行インデックス）、perimeter := 0（周囲長の合計）で初期化する
• height := 行数、length := 列数 を取得する
• 行列の各行について以下を繰り返す
  • c := 0（列インデックス）で初期化する
  • 行内の各値について以下を繰り返す
    • 値が1の場合
      • surround := 4 とする
      • c が length - 1 でない場合、右隣 matrix[d][c + 1] が1なら surround を1減らす
      • c が 0 でない場合、左隣 matrix[d][c - 1] が1なら surround を1減らす
      • d が height - 1 でない場合、下のセル matrix[d + 1][c] が1なら surround を1減らす
      • d が 0 でない場合、上のセル matrix[d - 1][c] が1なら surround を1減らす
      • perimeter := perimeter + surround
    • c := c + 1
• d := d + 1
• 最後に perimeter を返す

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

実装例

class Solution:
   def solve(self, matrix):
      d = 0
      perimeter = 0
      height = len(matrix)
      length = len(matrix[0])
      for line in matrix:
         c = 0

         for val in line:
            if val == 1:
               surround = 4
               if c != length - 1:
                  if matrix[d][c + 1] == 1:
                     surround -= 1
               if c != 0:
                  if matrix[d][c - 1] == 1:
                     surround -= 1
               if d != height - 1:
                  if matrix[d + 1][c] == 1:
                     surround -= 1
               if d != 0:
                  if matrix[d - 1][c] == 1:
                     surround -= 1
               perimeter += surround
            c += 1
         d += 1
      return perimeter

ob = Solution()
matrix = [
   [0,0,0,0,0],
   [0,0,1,1,1],
   [0,0,1,1,0],
   [0,1,1,1,0],
   [0,0,0,0,0]
]
print(ob.solve(matrix))

入力

matrix = [
[0,0,0,0,0],
[0,0,1,1,1],
[0,0,1,1,0],
[0,1,1,1,0],
[0,0,0,0,0]]

出力

14

補足：計算量と別のアプローチ

このアルゴリズムの計算量は O(行数 × 列数) です。すべてのセルを一度ずつ調べるだけで済むため、非常に効率的な手法といえます。

また、別の視点として「1のセルの総数 × 4 − 隣接しているペアの総数 × 2」という式でも周囲長を求められます。これは、隣接する2つのセルが互いに1辺ずつ外周から失うためです。どちらの方法でも同じ結果が得られるので、実装しやすい方を選ぶとよいでしょう。