---
title: "200. Number of Islands"
url: "https://laigary.com/interview/coding/200-number-of-islands"
type: "note"
section: "coding"
date: "2023-01-27"
updated: "2026-07-28"
tags: ["Graph", "Breadth-First Search", "Depth-First Search"]
---

# 200. Number of Islands

[200\. Number of Islands](https://leetcode.com/problems/number-of-islands/)

給一個由 `'1'`（陸地）和 `'0'`（水）組成的二維網格，算出有幾座島。上下左右相連的陸地算同一座島。

## 思路

這一題的重點在於於圖形中，進行深度優先搜索或是廣度優先搜索的遍歷。

第一步是**把網格翻譯成圖**：每一格是一個節點，上下左右相鄰的兩格之間有一條邊。翻譯完之後，「有幾座島」就是「這張圖有幾個連通分量」—— 一個標準的圖論問題。網格題幾乎都可以這樣翻譯，翻譯完就不必再把它當成「格子」來想。

今天的題目條件在於，如果一個陸地屬於一個島嶼的話，那該陸地一定是與其他陸地的四個方向之一有相連。要計算出有幾個島嶼，我只要站在島嶼上的任何一塊陸地，把該島嶼全部都標記成已經造訪過，那我就可以確定這個島嶼已經造訪完畢，計數器加一，接著再繼續找到下一個尚未被標記的陸地即可。

所以外層是一個雙重迴圈掃過整個網格，**只有踩到「還沒被標記的陸地」時才計數 +1**，然後立刻把整座島淹掉。淹掉這件事用 DFS 或 BFS 都可以，這也是為什麼這題是練這兩種遍歷的招牌題。

### 兩個容易忽略的點

**一、可以直接改 `grid` 當作 visited 嗎？**

把走過的陸地改成 `'#'`，就不用另外開一個 $O(mn)$ 的 `visited` 集合 —— 但代價是**破壞了輸入資料**。呼叫端如果還要用原本的網格就不能這樣做，那就多開一個 `visited` 集合，其他邏輯完全一樣。

**二、BFS 要在「入列」時標記，不是「出列」時。**

這是網格 BFS 最經典的 bug。如果只在出列時才標記，同一格可能被好幾個鄰居各自加進佇列一次，佇列會膨脹、時間退化。下面的 BFS 版本在 `queue.append` 的同一個 `if` 裡就把格子改成 `'#'`，就是為了這件事。

## 解題方向

### 深度優先搜索

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        
        def dfs(row, col):
            grid[row][col] = '#'
            for dr, dc in directions:
                next_row = row+dr
                next_col = col+dc
                if 0 <= next_row < rows and 0 <= next_col < cols and grid[next_row][next_col] == '1':
                    dfs(next_row, next_col)
                    
        islands = 0
        
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == '1':
                    islands += 1
                    dfs(row, col)
                    
        return islands 
```

`directions` 這個方向陣列是網格題的固定寫法，比展開成四段 `if` 好讀得多，而且要改成八方向（含對角線）只要多加四組。

**遞迴深度等於島的大小**，最壞情況是整張網格都是陸地。這題的網格上限是 300×300 = 90000 格，而 Python 預設的遞迴上限是 1000 —— 整張網格都是陸地時遞迴深度就是 90000，遠遠超過預設值（判題環境通常會調高）。這是 BFS 版在最壞情況下比較安全的原因。

### 廣度優先搜索

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        islands = 0
        
        def bfs(i, j):
            queue = deque([(i, j)])
            while queue:
                row, col = queue.popleft()
                grid[row][col] = '#'
                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == "1":
                        queue.append((new_row, new_col))
                        grid[new_row][new_col] = '#'

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    islands += 1
                    bfs(i, j)
                    
        return islands
```

注意 `queue.append(...)` 下面緊接著就是 `grid[new_row][new_col] = '#'` —— 這就是上面說的「入列即標記」。

BFS 版沒有遞迴，不會爆堆疊，所以**網格很大時 BFS 才是安全的選擇**。

## 補充

**Union-Find 也能解這題**（把每塊陸地和它的右邊、下面合併，最後數有幾個集合），但我沒有用這個角度寫過這題。同樣的手法見 [547. Number of Provinces](/interview/coding/547-number-of-provinces) 和 [323. Number of Connected Components](/interview/coding/323-number-of-connected-components-in-an-undirected-graph)。

**同一個骨架的網格題**：

- [695. Max Area of Island](/interview/coding/695-max-area-of-island) —— 不是數島，而是回傳每座島的大小取最大
- [1992. Find All Groups of Farmland](/interview/coding/1992-find-all-groups-of-farmland) —— 回傳每塊區域的邊界座標
- [417. Pacific Atlantic Water Flow](/interview/coding/417-pacific-atlantic-water-flow) —— 從邊界反過來往內灌
- [994. Rotting Oranges](/interview/coding/994-rotting-oranges)、[286. Walls and Gates](/interview/coding/286-walls-and-gates) —— **多源 BFS**：一開始就把所有起點都放進佇列，這類只能用 BFS，因為要的是最短時間

骨架整理見 [BFS / DFS 模板](/interview/coding/bfs-dfs-template)。

## 複雜度

**深度優先搜索**
- 時間 $O(mn)$ — 每一格最多被造訪一次（造訪後就變成 `'#'`，不會再進去）
- 空間 $O(mn)$ — 遞迴堆疊；最壞情況（整張網格都是陸地）深度等於格子數

**廣度優先搜索**
- 時間 $O(mn)$ — 同上，每格進出佇列各一次
- 空間 $O(\min(m, n))$ — 佇列裡最多裝下 BFS 波前的寬度，在網格上是 $O(\min(m,n))$

其中 `m`、`n` 是網格的列數和行數。

兩者時間相同，**差別在空間，而且 DFS 的那個 $O(mn)$ 是真的會炸的**（見上面的 `RecursionError`）。面試時可以先寫 DFS 因為比較短，但要主動說「如果網格很大我會改成 BFS，避免遞迴深度問題」。