Number of Islands
'1'（陸地）と '0'（水）からなる 2 次元グリッド grid が与えられる。島の数を返す。島は水で囲まれた陸地の連結成分。
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
grid[i][j]は'0'か'1'
使用した概念BFS
アプローチ
思考
- 未訪問の
'1'を見つけたらカウントを増やし、DFS で連結する陸地をすべて'0'に塗りつぶす - グリッドを直接書き換えて訪問済み管理を行う
実装
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0'
dfs(r + 1, c); dfs(r - 1, c)
dfs(r, c + 1); dfs(r, c - 1)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return countTime Space