# 刷題筆記 - LeetCode 200. Number of Islands
https://leetcode.com/problems/number-of-islands
## Thoughts
這題是要找出總共有多少個島嶼，如果是島嶼的話會是 `"1"` 表示，而 `"1"` 上下左右如果也有 `"1"` 的話，代表它們是同一個島嶼。
Example 2:
```
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
```
題目中的例子可以看出 `(2, 2)` 為 `"1"`，但 `(1,2), (3,2), (2, 1), (2, 3)` 皆是 `"0"`，這個 `"1"` 不與其他 `"1"` 相連，構成一個獨立島嶼。
問題在我們必須遍歷所有的元素，如果遇到 `"1"` 就代表我們遇上了島。
但不能單純遇到 `"1"` 就當成 1 個島，必須確認這個 `"1"` 是否與其他的 `"1"` 相連。
所以問題是 -
1. 可以雙層迴圈遍歷，但要怎麼確認上下左右也是 `"1"`
2. 如果確認上下左右是 `"1"`，勢必會有重疊的部分，要怎麼記錄
## Solution 1 - DFS, Recursion
### Logic
我們可以寫一個遞迴的 function，訪問每個點後，再去訪問這個點的上下左右四個點。
但遇到邊界、或是遇到 `"0"` 的時候，就該停止訪問。
而如果我們遍歷每個點，然後訪問島的上下左右，極有可能我們會重複訪問到同一個點。但我們已經檢查過上下左右的點，我們不會想再檢查一次，因此必須將訪問過的點做標記。而前述停止訪問的條件，也要考慮現在這個點是不是我們已經走過的點。
遞迴的 function 寫好後，我們要怎麼計算島嶼數量？
從第一個點開始，判斷 `(0, 0)` 是否為 `1`，先假設`(0, 0)` 是單獨一個島，附近都是水
→ 判斷是否為 `"1"`，執行 `dfs(0, 0)`
→ 檢查 `(0, 0)` 的上下左右，也就是 `(-1, 0), (1, 0), (0, -1), (0, 1)`
→ 執行 `dfs(-1, 0)` → 超過邊界，返回
→ 執行 `dfs(1, 0)` → `(1, 0) == "0"`，返回
→ 執行 `dfs(0, -1)` → 超過邊界，返回
→ 執行 `dfs(0, 1)` → `(0, 1) == "0"`，返回
→ 在這個 function 中確認從這個點開始，可以繼續往上下左右訪問的話，就先做標記，
這邊可以令 `(0, 0)` 等於 `"2"` (or `"0"`, 看個人喜好)
全部執行完後返回，這時島嶼數量就可以 +1，再去走下一個點 `(0, 1)`
### Code
```python=
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
islands = 0
def dfs(i, j):
if (i < 0 or i > rows - 1 or j < 0 or j > cols - 1
or grid[i][j] != "1"):
return
grid[i][j] = "2"
dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == "1":
dfs(i, j)
islands += 1
return islands
```
- 首先取得島嶼的列數與行數 (`rows` & `cols`)
- 然後定義遞迴的 function
- function 內先確認現在這個點是不是要繼續往下訪問，所以如果
1. x 座標超過邊界 `0 ~ (rows-1)`
2. y 座標超過邊界 `0 ~ (cols-1)`
3. 是水或者是訪問過的點 `"0" or "2" --> grid[i][j] != "1"` 就返回
- 假設可以繼續訪問，先把 `grid[i][j]` 標記為 `"2"`
- 再來繼續確認這個點的上下左右
- 最後全部都走完，返回到迴圈內，`islands` 就能加 1
**加上 `print(...)` 版本的程式碼**
```python!=
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
islands = 0
def dfs(i, j, depth = 0):
print(f"{' '*depth}DFS visiting: ({i}, {j}), value: {grid[i][j] if 0 <= i < rows and 0 <= j < cols else 'out of bounds'}")
if (i < 0 or i > rows - 1 or j < 0 or j > cols - 1 or grid[i][j] != "1"):
print(f"{' '*depth}Stopping at ({i}, {j}) - out of bounds or not '1'")
return
grid[i][j] = "2"
print(f"{' '*depth}Marked ({i}, {j}) as visited (changed to '2')")
dfs(i-1, j, depth + 1)
dfs(i+1, j, depth + 1)
dfs(i, j-1, depth + 1)
dfs(i, j+1, depth + 1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == "1":
print(f"\nStarting new island search at ({i}, {j})")
dfs(i, j)
islands += 1
print(f"Finished island, current count: {islands}")
print("Current grid state:")
for row in grid:
print(row)
return islands
```
可以跑 Testcase 觀察 Output:
Input
```
[["1","0","0","0"],
["0","1","1","1"],
["1","0","0","1"]]
```
Output
```
Starting new island search at (0, 0)
DFS visiting: (0, 0), value: 1
Marked (0, 0) as visited (changed to '2')
DFS visiting: (-1, 0), value: out of bounds
Stopping at (-1, 0) - out of bounds or not '1'
DFS visiting: (1, 0), value: 0
Stopping at (1, 0) - out of bounds or not '1'
DFS visiting: (0, -1), value: out of bounds
Stopping at (0, -1) - out of bounds or not '1'
DFS visiting: (0, 1), value: 0
Stopping at (0, 1) - out of bounds or not '1'
Finished island, current count: 1
Current grid state:
['2', '0', '0', '0']
['0', '1', '1', '1']
['1', '0', '0', '1']
Starting new island search at (1, 1)
DFS visiting: (1, 1), value: 1
Marked (1, 1) as visited (changed to '2')
DFS visiting: (0, 1), value: 0
Stopping at (0, 1) - out of bounds or not '1'
DFS visiting: (2, 1), value: 0
Stopping at (2, 1) - out of bounds or not '1'
DFS visiting: (1, 0), value: 0
Stopping at (1, 0) - out of bounds or not '1'
DFS visiting: (1, 2), value: 1
Marked (1, 2) as visited (changed to '2')
DFS visiting: (0, 2), value: 0
Stopping at (0, 2) - out of bounds or not '1'
DFS visiting: (2, 2), value: 0
Stopping at (2, 2) - out of bounds or not '1'
DFS visiting: (1, 1), value: 2
Stopping at (1, 1) - out of bounds or not '1'
DFS visiting: (1, 3), value: 1
Marked (1, 3) as visited (changed to '2')
DFS visiting: (0, 3), value: 0
Stopping at (0, 3) - out of bounds or not '1'
DFS visiting: (2, 3), value: 1
Marked (2, 3) as visited (changed to '2')
DFS visiting: (1, 3), value: 2
Stopping at (1, 3) - out of bounds or not '1'
DFS visiting: (3, 3), value: out of bounds
Stopping at (3, 3) - out of bounds or not '1'
DFS visiting: (2, 2), value: 0
Stopping at (2, 2) - out of bounds or not '1'
DFS visiting: (2, 4), value: out of bounds
Stopping at (2, 4) - out of bounds or not '1'
DFS visiting: (1, 2), value: 2
Stopping at (1, 2) - out of bounds or not '1'
DFS visiting: (1, 4), value: out of bounds
Stopping at (1, 4) - out of bounds or not '1'
Finished island, current count: 2
Current grid state:
['2', '0', '0', '0']
['0', '2', '2', '2']
['1', '0', '0', '2']
Starting new island search at (2, 0)
DFS visiting: (2, 0), value: 1
Marked (2, 0) as visited (changed to '2')
DFS visiting: (1, 0), value: 0
Stopping at (1, 0) - out of bounds or not '1'
DFS visiting: (3, 0), value: out of bounds
Stopping at (3, 0) - out of bounds or not '1'
DFS visiting: (2, -1), value: out of bounds
Stopping at (2, -1) - out of bounds or not '1'
DFS visiting: (2, 1), value: 0
Stopping at (2, 1) - out of bounds or not '1'
Finished island, current count: 3
Current grid state:
['2', '0', '0', '0']
['0', '2', '2', '2']
['2', '0', '0', '2']
```
最後輸出為 3
### Time & Space Complexity
- Time: O(m * n)
- 2 層迴圈，每個點最多只會被拜訪一次，所以最多拜訪所有點一次
- m: number of rows in the grid
- n: number of columns in the grid
- Space: O(m * n)
- 此解法沒有運用到額外的 visited matrix 來儲存訪問過的點，我們直接修改原本的 `gird` 將 `"1"` 標記為 `"2"`
- 但 call stack 最壞情況下仍是 O(m * n)。假設整個 grid 都是 `"1"`，遞迴會持續呼叫，最多會呼叫到 `m * n` 層，也就是每個點都進入一次遞迴，因此空間複雜度會是 O(m * n)
## Solution 2 - DFS, Stack
(working)
### Logic
### Code
### Time & Space Complexity
## Solution 3 - BFS, Queue
(working)
### Logic
### Code
### Time & Space Complexity
Sign in with Wallet
Connect another wallet