Number of Islands (DFS/BFS)
กำหนด Binary Matrix หาจำนวน "เกาะ" (Island) ที่เป็นกลุ่ม 1 ติดกันแนวนอน/แนวตั้ง (ไม่ใช่แนวทแยง) รอบนอกถือเป็นน้ำ (0)
อัลกอริทึม DFS (Flood Fill)
- วนทุกเซลล์ หากเจอ
1เพิ่มจำนวนเกาะ และเรียก DFS/BFS ทำให้เซลล์นั้นและเพื่อนบนที่เป็น 1 กลายเป็น 0 (ทำให้เป็นน้ำ) - DFS 4 ทิศทาง: บน, ล่าง, ซ้าย, ขวา
โค้ดตัวอย่าง Python
class Solution:
def numIslands(self, grid):
if not grid: return 0
n, m = len(grid), len(grid[0])
ans = 0
def dfs(i, j):
if i<0 or j<0 or i>=n or j>=m or grid[i][j]=='0':
return
grid[i][j] = '0'
dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1)
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
ans += 1
dfs(i, j)
return ans
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
print(Solution().numIslands(grid)) # 3
