[LeetCode] 200. Number of Islands

前言

---

　　這題是一個經典的 DFS 深度優先搜尋問題，聽說是 FAANG 高頻題(?，目標是在二維陣列裡找到連續出現 1 的範圍 (島嶼)，計算島嶼共出現幾個，這題有使用到兩個 for 迴圈加上遞迴，如果遞迴深度是固定的且不隨著輸入的增加而增加，而遞迴的深度和節點訪問僅發生一次，則遞迴的時間複雜度可以被忽略，時間複雜度估算為 O(n)，這裡有 JAVA 和 Python 的寫法。

題目

---

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

給定一個 m x n 的 2D 二進制網格 grid ，他代表 '1' 是陸地 '0' 是水的一張地圖，回傳這座島的數量。
一座島被水包圍，通過水平或垂直連結鄰近的土地而形成。你可以認為網格的全部四個邊都被水包圍。

題目連結：https://leetcode.com/problems/number-of-islands/

題目限制

---

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '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

左上角 9 個 1 連續在一起，共 1 座島嶼

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

左上角 4 個 1、中間 1 個 1、右下角 2 個 1，共 3 座島嶼

思路&筆記

---

快速地說是用雙迴圈找到了第一個 1，之後用 DFS 深度優先搜尋找他周圍是不是也是 1，然後當次的 DFS 完整跑完代表這個 Islands 的周圍全都是 0 了，可以用雙迴圈繼續找尋下一個 1 的位置 (第二個 Islands)

• 用雙迴圈依依找尋是 Islands 的索引 (是 1 的元素)
• 找到 Islands 後執行 DFS 深度優先搜尋，去找位於這個 Islands 索引的上下左右的索引是不是也是 1 (連續是 1 代表是同一個 Islands )
• 如果上下左右的索引不是 1 的話，而且自己也不是 1的話直接 return 出去，終止這次的 DFS
• 如果是 1 的話就換成 0，避免之後重複計算
• 執行完當次的 DFS，代表這個 Islands 上下左右都是 0，計算了這個 Islands 的數量後
• 直到雙迴圈再找到下一個 1 才會進去算到第二個 Islands (以此類推)

JAVA 實現

---

class Solution {
    public int numIslands(char[][] grid) {

        int count = 0; // 計算 Islands 的數量
        if (grid.length == 0) return 0; // 如果沒答案回傳 0

        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++) // 因為每個二維陣列的長度一樣
                // 如果是 '1' 就是 Islands
                if (grid[i][j] == '1') {
                    DFS(grid, i, j); // 使用深度優先搜尋後
                    count++; // 當下的 DFS 完全找完後記得 Islands 數量要加
                }
        }    
        return count;
    }

    // i < 0：表示越過了二維陣列的上方邊界。
    // j < 0：表示越過了二維陣列的左方邊界。
    // i >= grid.length：表示越過了二維陣列的下方邊界。
    // j >= grid[0].length：表示越過了二維陣列的右方邊界。
    // grid[i][j] != '1'：表示遍歷的點不是陸地（可能是水，或者已經被訪問過的陸地）。

    private void DFS(char[][] grid, int i, int j) {

        // 上下左右是 0 的話不做任何事 (停止的意思)，確保我們只對合法的陸地格子執行 DFS 遞迴搜索
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') return;
        grid[i][j] = '0'; // 把遍歷到的陸地 1 換成 0，避免重複計算成 Islands

        // 遞迴
        DFS(grid, i + 1, j); // 找尋四個方向的下方
        DFS(grid, i - 1, j); // 找尋四個方向的上方
        DFS(grid, i, j + 1); // 找尋四個方向的右方
        DFS(grid, i, j - 1); // 找尋四個方向的左方
    }
}

Python 實現

---

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        # 如果沒答案回傳 0
        if not grid or not grid[0]:
            return 0

        count = 0 # 計算 Islads 數量

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 如果是島嶼的話
                if grid[i][j] == '1':
                    self.DFS(grid, i, j) # 使用 DFS 深度優先搜尋
                    count += 1

        return count

    def DFS(self, grid: List[List[str]], i: int, j: int) -> int:
        # 索引：上邊界、下邊界、左邊界、右邊界、自己，上下左右是 0 的話不做任何事 (停止的意思)
        if i<0 or j<0 or j>=len(grid[0]) or i>=len(grid) or grid[i][j] != '1':
            return
        
        grid[i][j] = '0' # 設置為 0，避免重複計算
        
        self.DFS(grid, i-1, j) # 上
        self.DFS(grid, i+1, j) # 下
        self.DFS(grid, i, j-1) # 左
        self.DFS(grid, i, j+1) # 右

成績

---

Language	Runtime	Memory
Java	3ms	47.3MB
Python	274ms	18.9MB

參考資料

---

DFS 深度優先搜尋：https://www.youtube.com/watch?v=U3IpByPjKtU&t=1s