กำหนด grid 2D ของ '1' (บก) และ '0' (น้ำ) นับจำนวนเกาะ (connected component แบบ 4-direction)
ตัวอย่าง
grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
อัลกอริทึม DFS / BFS
- วนทุกเซลล์ ถ้าเจอ '1' → เพิ่ม count และ DFS/BFS ทำให้เป็น '0' (น้ำ) ทั้ง component
- DFS เรียกซ้ำ 4 ทิศทาง
โค้ด DFS
class Solution:
def numIslands(self, grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0' # mark visited
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
# ทดสอบ
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
sol = Solution()
print(sol.numIslands(grid)) # 3
ความซับซ้อน
- Time: O(m×n) ทุกเซลล์ถูกเยี่ยมสูงสุด 1 ครั้ง
- Space: O(m×n) เรียกซ้ำ (worst case ทั้ง grid เป็นบก)
สรุป
DFS flood fill เป็นวิธีมาตรฐานสำหรับ connected components ใน grid
