17. Number of Islands

読了目安約2分

Graph / LeetCode 200 (Medium) — 見つけた陸地を DFS で塗りつぶしながら島を数える。

この章の目次

問題

LeetCode 200. Number of Islands（Medium / カテゴリ: Graph）

"1"（陸）と "0"（海）からなるグリッドが与えられます。上下左右に隣り合う陸のかたまりを島と数えます。斜めはつながりません。島がいくつあるかを返します。

考え方

ヒント 1

全マスを順に見て、陸を見つけたら島を 1 つ数えます。同じ島を二度数えないための工夫が必要です。

ヒント 2

陸を見つけたら、そこから深さ優先探索（DFS）でつながる陸をすべて "0" に塗りつぶします。塗りつぶした島は以後の走査で見つからないので、各島はちょうど 1 回だけ数えられます。幅優先探索（BFS）でも同じように解けます。

Swift 実装のポイント

引数の grid はそのままでは書き換えられません。var grid = grid でコピーを作ります。
要素は Character なので、比較は grid[r][c] == "1" と書けます。
DFS を入れ子関数にすると、grid や縦横のサイズを引数で回さずに済みます。
範囲外と海のチェックは guard 1 行にまとめると再帰が短く書けます。

模範解答

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

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

        for r in 0..<h {
            for c in 0..<w where grid[r][c] == "1" {
                count += 1
                sink(r, c)
            }
        }
        return count
    }
}

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