Number of Islands
同じ長さの文字列のリストとしてマップが与えられます。'1'は陸地のマス、'0'は水のマスです。上下左右のいずれかの辺を共有する陸地のマスは、同じ島に属します。角だけで接しているマスはつながっていません。島の数を返してください。
関数
- gridstring-array
- マップは、1行につき1つの文字列
- 戻り値integer
- 島の数
制約
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- すべての行の長さは同じです。
- すべての文字は
'0'または'1'です。
例
- 入力
- grid = ["11000", "11000", "00100", "00011"]
- 出力
- 3
- 説明
- 左上の4つのマスは、1つの島を形成しています。3行目の中央のマスは角でしか接していないため、2つ目の島です。右下の2つのマスが3つ目です。
- 入力
- grid = ["01110", "01000", "00011", "11001"]
- 出力
- 3
- 説明
- 上段の3つのマスと、その左端の下にある1つのマスが1つの島を形成します。3段目の右側の2つのマスは下の右端のマスにつながり、2つ目の島になります。下段の左側の2つのマスが3つ目です。
発展問題
陸地は今、水の地図上に一マスずつ現れます。地図全体をもう一度調べずに、新しいマスが追加されるたびに島の数を報告できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
地図をマスごとに調べます。それまでの島に属していない陸地のマスにたどり着いたとき、新しい島はいくつ見つかりましたか？
新しい島を見つけたら、その島につながっているすべての陸地のマスを訪れて、それぞれを確認済みとして印を付けます。そうすれば、スキャンで同じ島を再び数えることはありません。
まだ訪れていないマスを、キュー（幅優先）または明示的なスタック（深さ優先）を使って探索します。巨大な島が1つだけある地図では、再帰探索はコールスタックを使い切ることがありますが、自分で用意したキューやスタックを使うループならその心配はありません。
解説
陸地の各マスを、隣接する陸地のマスとつながったノードとして扱います。島とは、ひと続きにつながった領域です。地図を走査し、まだ見ていない陸地に到達するたびに新しい島として数え、その島を塗りつぶし探索して、すべてのマスに印を付けます。これにより、走査中に同じ島を再び数えることはありません。
明示的なスタックを使ったフラッドフィル（DFS）
考え方
印の付いていない陸地のマスは、すでに数えた島に属することはありません。島を数えると、その全体に印を付けるからです。つまり、それは新しい島です。自分で管理するスタックを使って残りにも印を付けます。取り出した各マスは、印の付いていない陸地の隣接マスをスタックに追加し、スタックが空になったとき、島全体に印が付いています。
自分のスタックを使うことが重要です。陸地だけの 150 × 150 のマップでは、再帰的な塗りつぶしの呼び出しが 22,500 回まで深くなる可能性があるからです。各マスは最大 1 回スタックに追加され、4 つの隣接マスを調べるため、時間計算量は O(rows × cols) です。マップがすべて陸地の場合、印とスタックに必要な空間計算量は O(rows × cols) です。
アルゴリズム
- すべてのマスに訪問済みの印を付け、カウントを0に設定します。
- 水のマスと、すでに訪問済みのマスを飛ばしながら、すべてのマスを調べます。
- 未訪問の陸地では、カウントに1を加え、そのマスに印を付けてスタックに追加します。
- スタックが空でない間、マスを1つ取り出し、マップ内にある未訪問の陸地の隣接マスそれぞれに印を付けてから、スタックに追加します。
- 走査が終わったら、カウントを返します。
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return countキューを使った塗りつぶし（BFS）
考え方
カウントの仕組みは同じで、訪問順序だけが変わります。キューは先頭からマスを取り出し、印の付いていない隣接する陸地を末尾に追加するため、島を輪状に訪問します。最初のマス、次に1歩離れたすべてのマス、そして2歩離れたすべてのマス、という順です。各マスは依然として1回だけ訪問され、時間計算量と空間計算量は O(rows × cols) です。
輪状の順序によって各マスの開始地点からの距離が分かるため、同じループで、各マスに数値を1つ追加するだけで、グリッド上の最短経路に関する問いに答えられます。
アルゴリズム
- すべてのマスに訪問済みマークを作成し、カウントを0に設定します。
- 水域と、すでに訪問済みのマスを飛ばしながら、すべてのマスを調べます。
- 未訪問の陸地を見つけたら、カウントに1を加え、そのマスにマークを付けて空のキューに入れます。
- キューにマスがある間、先頭から1つ取り出し、マップ内にある隣接マスのうち未訪問の陸地を、マークを付けながらキューの末尾に追加します。
- 調査が終わったら、カウントを返します。
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
落とし穴と境界ケース
- マスをスタックやキューに入れるときではなく、取り出すときに印を付けること。同じマスが何度も入ることになります。
- マスを文字
'1'ではなく数値 1 と比較すること。各行は文字列なので、各マスは文字です。 0 ≤ row < rowsと0 ≤ col < colsを確認する前に、隣のマスを読み取ること。すると、端にある陸地のマスで地図の範囲外を読み取ってしまいます。- 塗りつぶしを再帰的に書くこと。Python はデフォルトで 1,000 回の呼び出しで停止し、ほかの言語では大きな島ひとつでスタックがオーバーフローすることがあります。
pop(0)を使って Python のリストの先頭を取り出すこと。リストの長さに比例した時間がかかります。代わりにcollections.dequeとpopleft()を使いましょう。
よくある質問4
島の数の時間計算量はどれくらいですか？
O(rows × cols)。走査では各マスを1回ずつ確認し、各陸地のマスはスタックまたはキューに1回追加され、4つの隣接マスを確認します。すべてが陸地のマップでは、訪問済みの印とスタックまたはキューに O(rows × cols) の領域を使用します。
島の数を求めるには、BFSとDFSのどちらを使うべきでしょうか？
どちらも時間と空間の面で正しいです。数えるには、島の各マスに印を付ければよいだけだからです。キューを使うBFSは再帰を使いません。明示的なスタックを使うなら、DFSも同様に安全です。
union-find を使って Number of Islands を解けますか？
陸地の各マスをそれぞれ独立した集合に入れ、陸地のマスの数を初期カウントにします。隣接する陸地のマスの各ペアを結合し、結合によって異なる2つの集合がつながるたびに、カウントを1減らします。経路圧縮を使うと、実行時間は O(rows × cols) に近くなります。
別個の seen 配列なしで島の数を数えられますか？
はい、地図を変更してもよいなら可能です。各陸地のマスに到達したら、すぐに水に変えます。多くの言語では文字列をその場で変更できないため、まず各行を文字のグリッドにコピーしますが、必要な領域は訪問済みの印と同じです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def numIslands(grid):
# ここにコードを記述してくださいテスト #1
テスト #2
引数
grid = ["11000", "11000", "00100", "00011"]
期待される出力
3