18. Max Area of Island

読了目安約2分

Graph / LeetCode 695 (Medium) — DFS の戻り値で面積を集計し、最大の島を求める。

この章の目次

問題

LeetCode 695. Max Area of Island（Medium / カテゴリ: Graph）

0（海）と 1（陸）からなるグリッドが与えられます。上下左右につながる陸のかたまりを島とし、最大の島の面積を返します。面積は島に含まれるマスの数で、島が 1 つもなければ 0 を返します。

考え方

ヒント 1

Number of Islands と同じ塗りつぶしです。数えるものが「島の個数」から「島の面積」に変わります。

ヒント 2

深さ優先探索（DFS）を「そのマスから広がる面積を返す関数」として書きます。自分の 1 マスに上下左右の再帰の結果を足して返し、全マスから試した最大値を取ります。

Swift 実装のポイント

訪れた陸を 0 に書き換えれば、訪問済みを覚える配列は要りません。
面積は 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1) と戻り値の合計で書けます。
範囲外と海で 0 を返すようにすると、呼び出し側の場合分けが消えます。

模範解答

Swift
class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        var grid = grid
        let h = grid.count
        let w = grid[0].count

        func area(_ r: Int, _ c: Int) -> Int {
            guard r >= 0, r < h, c >= 0, c < w, grid[r][c] == 1 else { return 0 }
            grid[r][c] = 0
            return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1)
        }

        var best = 0
        for r in 0..<h {
            for c in 0..<w {
                best = max(best, area(r, c))
            }
        }
        return best
    }
}

計算量: O(hw)（h は行数、w は列数。各マスを定数回ずつ見ます）。