1 題目描述

一個二維數組，把 1 看做陸地，把 0 看做大海，陸地相連組成一個島嶼。把陣列以外的區域也看做是大海，問總共有多少個島嶼。

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

2 解法

這個解法主要有兩個：

  1. DFS：就是深入檢查每個node是否有相連，如果有就把相連的部分都變成0，直到沒有相連的部分為止。
  2. 併查集 Disjoint-set data structure: 利用尋找root的方式，如果發現有共同的祖先，那就表示這兩個land是相連的，如果是不同的root就代表不同祖先，可能要建立bridge或是union合併。

DFS的方法比較簡單明瞭，併查集的方法比較複雜，但是很有趣，所以我兩個都會來說明如何實現。

2.1 DFS

基本上在上下左右探索的時候，要確保三個原則：

  1. 不要超出rows邊界
  2. 不要超出cols邊界
  3. 不要走到海洋
1
2
3
4
5
6
7
8
9
10
11
def dfs(i, j):
    # (不要超過 rows) or (不要超過cols) or (走到海洋) 否則什麼都不做
    if (i < 0 or i >= len(grid)) or (j < 0 or j >= len(grid[0])) 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)

開始檢查陸地，如果發現陸地，先num_islands += 1，然後開始DFS探索。

1
2
3
4
5
6
7
8
9
10
11
12
def numIslands(self, grid: List[List[str]]) -> int:
    if not grid:
        return 0

    num_islands = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                num_islands += 1
                dfs(i, j)

    return num_islands

完整的程式碼如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""
Time: O(M * N)
- M 與 N 分別是 rows 與 cols
- 因為每個元素都會被訪問一次，所以時間複雜度是 O(M * N)

Space: O(M * N)
- 空間複雜度來自遞歸的深度，最壞情況下是整個地圖都是陸地，所以是 O(M * N)
"""
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            if (i < 0 or i >= len(grid)) or (j < 0 or j >= len(grid[0])) 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)

        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    num_islands += 1
                    dfs(i, j)

        return num_islands

2.2 併查集

在開始之前我先來說個故事，目前這個城市有三個幫派，分別是BossA, BossB, BossC，老大底下有一些小弟用P來表示。

當兩個小弟遇見的時候，如果發現他們的共同老大都是相同的，例如BossA，那就不會打架，畢竟是同一個幫派的。

但是當兩個小弟遇見的時候，發現他們的老大不一樣，例如BossA和BossB，那就會打架，因為他們是不同幫派的。

你會發現，我們在找Boss的時候，每次一層層往上找太麻煩了，如果我們在找的過程中，就慢慢把組織扁平化，變成兩層不就很好找嗎？

然後打架打完，總會有輸贏，輸的一方要合併進去另一個幫派。

在上面的故事中，主要牽涉兩個動作，我們可以利用這個特性去找到有多少個land。

  1. Find 尋找老大是誰
  2. Union 老大不同的時候，要合併兩個幫派

Step1. 先假設每個小弟node都獨自一個幫派，他們的parent（老大）都是自己。

  • 島嶼的數量就是所有boss的數量。

Step2. 我們發現小弟0號是島嶼，因此開始檢查周邊是不是有島嶼相連，如果有就合併。

  • 我們發現小弟5號是島嶼，因此小弟5號的parent指定為小弟0號。
  • lands 這時候 -1 代表有一個島嶼被合併了。

Step3. 繼續檢查周邊是不是有島嶼相連，如果有就合併。

  • 小弟0號的左邊也是島嶼，因此小弟1號的parent指定為小弟0號。
  • lands 這時候 -1 代表有一個島嶼被合併了。

Step4. 這時候小弟0號都檢查完畢，換下一個小弟1號，繼續檢查周邊是不是有島嶼相連，如果有就合併。

  • 發現小弟6號也是島嶼，而小弟0號的老大是1號，因此小弟6號的parent指定為小弟0號。這就是我們說的階級兩層化。
  • lands 這時候 -1 代表有一個島嶼被合併了。

Step5. 繼續尋找下一個島嶼，找到小弟5號，但是因為小弟5號下面是海洋，所以不用合併。

Step6. 但是小弟5號的左邊是島嶼，所以進行合併

  • 但是發現小弟5號的老大是小弟0號，而小弟6號的老大也是小弟0號，所以不用做任何事情。

Step7. 繼續尋找下一個島嶼，找到小弟12號，但是下面跟右邊都是海洋，所以不用處理，他獨自當老大。

Step8. 繼續尋找下一個島嶼，找到小弟18號，因為下面是海洋，所以我們只要檢查左邊即可。

  • 左邊的小弟19號是島嶼，並且他與小弟18的parent不同，因此進行合併。
  • lands 這時候 -1 代表有一個島嶼被合併了。

寫成程式碼的邏輯就是如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class UnionFind:
    def __init__(self, grid, rows, cols):
        self.nums = 0
        # 記錄 '1' 的個數作為初始的島嶼數量
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    self.nums += 1

        # 每個節點初始化為它本身，每個人都是自己的老大 parent
        total_nodes = rows * cols
        self.parents = [i for i in range(total_nodes)]

    # 當發現兩個小弟的parent不同時，進行合併
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 發生合併時，nums 減 1（島嶼-1）
        if root1 != root2:
            self.parents[root2] = root1
            self.nums -= 1
    
    # 尋找老大 parent 是誰
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]  # 路徑壓縮
            node = self.parents[node]
        return node

    # 取得當前島嶼的數量
    def get_nums(self):
        return self.nums

以下是呼叫的程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
Time: O(M * N * a(M * N))
- M 與 N 分別是 rows 與 cols
- a(M * N) 是 Ackermann 函數的反函數，是一個很慢的函數，隨著unionFind的路徑壓縮優化，他的值增長極慢，因此可以近似為 O(1) 常數

Space: O(M * N)
- parents 陣列，大小與grid的數量呈正比
"""
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        uf = UnionFind(grid, rows, cols)

        for row in range(rows):
            for col in range(cols):
                # 找到陸地，就開始檢查下面跟左邊是否為島嶼，如果是就合併
                if grid[row][col] == '1':
                    # 下面是陸地
                    if row < rows - 1 and grid[row + 1][col] == '1':
                        uf.union(self.node(row, col, cols), self.node(row + 1, col, cols))
                    # 左邊是陸地
                    if col < cols - 1 and grid[row][col + 1] == '1':
                        uf.union(self.node(row, col, cols), self.node(row, col + 1, cols))

        return uf.get_nums()

    # 取得小弟的代號
    def node(self, i, j, cols):
        return i * cols + j

Ref