---
# System prepended metadata

title: '**程式筆記(dfs)**'
tags: [graph, code, note]

---

# **程式筆記(dfs)**


:::info
:information_source: 日期 : 2023/06/29
:::


**:thumbsup:DFS** 

深度優先搜尋(Depth-First Search,DFS)
可以利用**堆疊Stack**的方式來處理

---
**dfs經典步驟(stack)**
1. 創造四個方向dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] 
visited為list或set
初始化stack型態
2. while record來帶入迴圈
(有可能在最上層就放 4.三個條件)
pop stack 最上層
3. 四個方向去找
4. 三個條件
    * r, c在範圍內
    * 沒在visit
    * 題目的限制條件
5. 通過後加入stack和visited


**dfs經典步驟(function)**
```python
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = set()

def dfs(r, c, i, visited):
    if 某一些要達成的條件:
        return True
    
    if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or 
        board[r][c] != word[i](某一些條件) or (r, c) in visited:
        return
            
    visited.add((r, c))
    
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if dfs(nr, nc, i + 1, visited): 
            return True 
        
    visited.remove((r, c))
    return


for r in range(len(board)):
    for c in range(len(board[0])):
        if dfs(r, c, 0, visited):
            return True
return False
```

---

**:thumbsup:DFS經典** 

* 尋找Parentheses(括號)組合
用dfs下去找，可以加右括號的條件 -> 左括號比較多時，可以加左括號的條件 -> 小於規定的n時，隨時都可以，每個組合都累積它的專屬路徑
```python
def dfs(r, l, path):
    if r == n and l == n:
        res.append(path)
        return
    if r < l: # (要比較多才可以開始加)
        dfs(r + 1, l, path + ")")
    if l < n: # 左邊無限加 
        dfs(r, l + 1, path + "(")
```
* word search
記得要remove，反例ex.想要找CE，一個C附近有多個E，在第一個E走不通時，要把走過的路徑清乾淨
![image](https://hackmd.io/_uploads/HyUVj4cnp.png =40%x)
```python
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.n, self.m = len(board), len(board[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = set()

        for r in range(self.n):
            for c in range(self.m):
                if self.dfs(r, c, 0, word, board, visited):
                    return True
        return False
        
    def dfs(self, r, c, i, word, board, visited):
        if i == len(word):
            return True
        if r < 0 or c < 0 or r >= self.n or c >= self.m or board[r][c] != word[i] or (r, c) in visited:
            return
        
        visited.add((r, c))
        for dr, dc in self.dirs:
            nr, nc = r + dr, c + dc
            if self.dfs(nr, nc, i + 1, word, board, visited):
                return True
        visited.remove((r, c))
        return False
```


* Number of Islands(island數量)
```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.res = 0
        self.n, self.m = len(grid), len(grid[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        self.visited = set()

        for r in range(self.n):
            for c in range(self.m):
                if self.dfs(grid, r, c):
                    self.res += 1
        return self.res 
    
    def dfs(self, grid, r, c):
        if r < 0 or r >= self.n or c < 0 or c >= self.m or (r, c) in self.visited or grid[r][c] == "0":
            return
        
        self.visited.add((r, c))
        
        for dr, dc in self.dirs:
            nr, nc = r + dr, c + dc
            self.dfs(grid, nr, nc)

        return True
```
* 最大island面積(Max Area of Island)
dfs需要回傳的是數字，不符合條件的回傳0，有被加到visited的為1，並在dfs中累積
![image](https://hackmd.io/_uploads/SykHLrc26.png =50%x)

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited = set()
        maxArea = 0

        def dfs(r, c):
            if r < 0 or c < 0 or r >= m or c >= n or (r, c) in visited or grid[r][c] == 0:
                return 0

            visited.add((r, c))
            curArea = 1

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                curArea += dfs(nr, nc)

            return curArea


        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1 and (r, c) not in visited:
                    maxtempArea = dfs(r, c)
                    maxArea = max(maxArea, maxtempArea)

        return maxArea
```
也可以**用一個全域函數**，來記錄area的大小，每次dfs完又設回初始值
```python
dfs函數
visited.add((r, c))
self.area += 1 # 這裡
for ...:
    ...
    dfs(nr, nc)
return

主函數
for ...:
    for ...:
        if ...:
            dfs(r, c)
            maxArea = max(maxArea, self.area)
            self.area = 0
return ...
```
* Pacific Atlantic Water Flow
從pac和atl的每個點去做dfs，從該點進入matrix，看能到達哪一點(代表那點和這個海洋互通)
同時也要記錄pre，這條dfs路徑的高度必須不停遞增，才可以通
```python
記得要創造空matrix是先n再m
m, n = len(heights), len(heights[0])
pac = [[False] * n for _ in range(m)]
```

```python
def dfs(r, c, sea, pre):
    if r < 0 or c < 0 or r >= m or c >= n or sea[r][c] or heights[r][c] < pre:
        return

    sea[r][c] = True

    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        dfs(nr, nc, sea, heights[r][c])

    return


# 讓四邊海洋去跑dfs
for r in range(m):
    dfs(r, 0, pac, 0)
    dfs(r, n - 1, atl, 0)
for c in range(n):
    dfs(0, c, pac, 0)
    dfs(m - 1, c, atl, 0)

for r ...:
    for c ...:
        if pac[r][c] and atl[r][c]:
            檢查兩個都為True
```

* 改OX
也是從邊界出發，只要有和邊界相連的(dfs)，那就特別標註(後續不能改到)，剩餘的必定為不和邊界相連，無條件改成X
```python
邊界
for r in range(m):
    dfs(r, 0)
    dfs(r, n - 1)
for c in range(n):
    dfs(0, c)
    dfs(m - 1, c)
```

---

**:thumbsup:Course Schedule系列** 
需要remove需要remove需要remove

* 先修課程(Course Schedule)
只會有一個錯誤的條件，如果在dfs過程中，碰到正在visited中的課程(也就是在dfs這條路上的課程)，必定錯誤，因為代表這條路有互相引用的情況
遍歷每一個課程，然後不斷檢查每門課程前面所有的pre課程，任何衝突都沒有發生就可以回傳True
```
會需要remove，是因為可能會有

         1
0   -          -   3
         2
我們是從3走回去，用dfs會先走3-1-0，再來走3-2-0，
如果沒有remove的話，0會被標記為已經走過，會錯誤
```
```python
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        record = defaultdict(list)
        for cour, pre in prerequisites:
            record[cour].append(pre)
        
        for c in range(numCourses):
            visited = set()
            if not self.dfs(c, visited, record):
                return False
        return True

    def dfs(self, c, visited, record):
        if c in visited:
            return False
        if not record[c]:
            return True
        
        visited.add(c)
        for pre in record[c]:
            if not self.dfs(pre, visited, record):
                return False
        
        visited.remove(c)
        record[c] = []
        return True
```
```python
需要先建立有向圖dict
for cour, pre in prerequisites:
    graph[cour].append(pre)
```

```python
以下寫法為"嚴格dfs"，如果有任何一階回傳False，所有都會變False
if not dfs(pre):
    return False
```
* 先修課程二(Course Schedule II)
主要是需要同時檢查有無重複(visited)，也要排出路徑(重點是有多種可能)，所以也需要另外一個set(done)來記錄，如果已經被放到路徑裡的node，就不用再去查找
```python
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        record = collections.defaultdict(list)
        for cour, pre in prerequisites:
            record[cour].append(pre)
        
        done = set() # no violation but already added
        res = []
        visited = set()

        def dfs(c):
            if c in done:
                return True
            if c in visited:
                return False

            visited.add(c)
            for pre in record[c]:
                if not dfs(pre):
                    return False
            
            if c not in done:
                res.append(c)
                done.add(c)
            visited.remove(c)

            return True


        for c in range(numCourses):
            if not dfs(c):
                return []
        return res
```

---

**:thumbsup:有向圖dict系列** 
看到有向圖就建立dict

* 重現轉機行程(Reconstruct Itinerary)
因為不能用visited紀錄(同一個機場可能去好幾次)，所以直接pop掉dict中(起始機場, 終點機場)的這個行程，這個dict[起始機場] = 終點機場，如果這個dfs路徑不成功，再加回來，對待path也是一樣
```python
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for start, end in tickets:
            graph[start].append(end)
        
        self.path = ["JFK"]

        def dfs(airport):
            if len(tickets) + 1 == len(self.path):
                return True
            if not graph[airport]:
                return False

            # If there are multiple valid itineraries, you should return the itinerary 
            # that has the smallest lexical order
            for end in sorted(graph[airport]):
                graph[airport].remove(end)
                self.path.append(end)
                if dfs(end):
                    return True
                graph[airport].append(end)
                self.path.pop()

            return

        dfs("JFK")
        return self.path
```
當行程還沒有全部走過，但某一個機場不能飛到任何一個其他機場時(也就是這個dict[key]已經空了)，就return False
```python
以下寫法為"嚴格正確dfs"，一有一條路徑是True，就回傳True
if dfs(pre):
    return True
```
* Evaluate Division
類似找連除法的答案
只能說是一題很經典的題目，先前後紀錄鄰居與數值，後用dfs去查找連鎖關係
```
注意
1. 要有visited，否則會有迴圈ababa..
2. 字母不在record裡那就免談
3. 要用if end in record[start]:檢查
直接if record[start][end]會key error
4. 如果temp == -1為pass，還是去遍歷其它可能nei，而不是直接return
```

```python
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        record = defaultdict(dict)
        for (start, end) , val in zip(equations, values):
            record[start][end] = val
            record[end][start] = 1.0 / val

        res = []
        
        def dfs(start, end, visited):
            if start not in record or end not in record:
                return -1.0
            if start == end:
                return 1.0
            if end in record[start]:
                return record[start][end]
            
            visited.add(start)

            for nei in record[start]:
                if nei not in visited:
                    temp = dfs(nei, end, visited)
                    if temp == -1.0:
                        pass
                    else:
                        ans = record[start][nei] * temp
                        record[start][end] = ans
                        record[end][start] = 1/ans
                        return ans
            
            visited.remove(start)
            
            return -1.0
        
        for start, end in queries:
            val = dfs(start, end, set())
            res.append(val)
        
        return res
```


---

**:thumbsup:tree系列**

* Path Sum
要找有沒有從root到leaf的加總路徑
當沒有左右小孩的時候，就去檢查加法是否正確
非嚴格正確，如果有一個正確的，那就會傳True
```python
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.traverse(root, targetSum, 0)

    def traverse(self, node, targetSum, total):
        if not node:
            return False

        total += node.val
        if not node.left and not node.right and total == targetSum:
            return True

        return (self.traverse(node.left, targetSum, total) or self.traverse(node.right, targetSum, total))
```

* Time Needed to Inform All Employees
從上往下，從manager往下到employee，統計最長路徑，用res統計
![image](https://hackmd.io/_uploads/B1H_rkQB6.png)
![image](https://hackmd.io/_uploads/r1BbDvq2T.png =70%x)


```python
def __init__(self):
    self.res = float("-inf")
def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
    graph = collections.defaultdict(list)
    for emp, man in enumerate(manager):
        graph[man].append(emp)

    self.dfs(graph, informTime, headID, 0)
    return self.res

def dfs(self, graph, informTime, man, time):
    for emp in graph[man]:
        self.dfs(graph, informTime, emp, time + informTime[man])
    self.res = max(self.res, time)
```

* Construct Quad Tree
用兩個for迴圈去檢查，分為還可以繼續切分跟不可以繼續切分兩類，如果數字不同(可以繼續切分)，那就會越過if boolean判斷式，然後呼叫4個方位繼續尋找，如果數字相同，那if boolean為真，回傳Node(value, True)
```python
# Definition for a QuadTree node.
class Node(object):
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

        
# r & c is starting point
def dfs(n, r, c):
    value = grid[r][c]
    boolean = True
    for i ...:
        for j ...:
            if grid[r + i][c + j] != value:
                boolean = False # if can divide
                break

    if boolean: # if cannot divide anymore
        return Node(value, True)

    # if still can divide
    topL = dfs(n // 2, r, c)
    topR = dfs(n // 2, r, c + n // 2)
    bottomL = dfs(n // 2, r + n // 2, c)
    bottomR = dfs(n // 2, r + n // 2, c + n // 2)
    return Node(0, False, topL, topR, bottomL, bottomR)

# main function call
return dfs(len(grid), 0, 0)           
```

---

**:thumbsup:其他**

* Matchsticks to Square
用掉全部竹籤後，能組成一個完整正方形
從第一個數字開始，不停往下把arr中每個竹籤加到四邊(sides)，
```python
class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        length = sum(matchsticks) // 4
        if sum(matchsticks) != length * 4:
            return False
        
        side = [0] * 4

        # Reverse sort the matchsticks because we want to consider the biggest one first.
        matchsticks.sort(reverse=True)
        
        def dfs(i):
            if i == len(matchsticks):
                if side[0] == side[1] == side[2] == side[3] == length:
                    return True
                else:
                    return False
            
            for s in range(4):
                if side[s] + matchsticks[i] <= length:
                    side[s] += matchsticks[i]
                    if dfs(i + 1):
                        return True
                    side[s] -= matchsticks[i]

            return False

        return dfs(0)    
```
* Path With Minimum Effort
用binary search 去找目標最小值，用這個目標最小值去走dfs
```python
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        n, m = len(heights), len(heights[0])
        dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]

        def dfs(r, c, limitEffort):
            if r == n - 1 and c == m - 1:
                return True
            if r < 0 or c < 0 or r >= n or c >= m or (r, c) in visited:
                return False
            
            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m: # check if inside the boundary
                    if abs(heights[nr][nc] - heights[r][c]) <= limitEffort:
                        if dfs(nr, nc, limitEffort):
                            return True

        l, r = 0, 10 ** 6
        while l <= r:
            mid = (l + r) // 2
            visited = set() # has to renew it every time
            if dfs(0, 0, mid):
                r = mid - 1
            else:
                l = mid + 1

        return l
```
we could use Dijkstra's Algorithm which is used to find the shortest path in a weighted graph with a slight modification of criteria for the shortest path.
永遠先pop調最小effort的，無論和當前走的path沒任何關係，這樣能確保到達終點時，effort是最小值
![image](https://hackmd.io/_uploads/HJZAY6VIa.png =50%x)
```python
n, m = len(heights), len(heights[0])
dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
minHeap = [[0, 0, 0]] # [effort, r, c]
visited = set()

while minHeap:
    effort, r, c = heapq.heappop(minHeap)
    if r == n - 1 and c == m - 1:
        return effort

    visited.add((r, c))
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < m and (nr, nc) not in visited:
            newEffort = max(effort, abs(heights[r][c] - heights[nr][nc]))
            heapq.heappush(minHeap, [newEffort, nr, nc])
```
* Minimum Moves to Spread Stones Over Grid
先記錄zero有多少個，然後用dfs去遍歷每個大於2的數字，假設那個數字可以填補當下(step)那個0，預設這個假設成立，去走下一個zero裡面的數字
```python
n, m = len(grid), len(grid[0])
def distance(a, b):
    a1, a2 = a[0], a[1]
    b1, b2 = b[0], b[1]
    return abs(a1 - b1) + abs(a2 - b2)

# step : what pair of [r, c] in zero we are dealing with
def dfs(step):
    if step == len(zero): # finish filling
        return 0

    result = float("inf")
    zero_r, zero_c = zero[step][0], zero[step][1]
    # find non-zero 
    for r in range(n):
        for c in range(m):
            if grid[r][c] >= 2:
                grid[r][c] -= 1
                result = min( result, distance((r, c), (zero_r, zero_c)) + dfs(step + 1) )
                grid[r][c] += 1 # need to try other

    return result

# record the zero
zero = []
for r in range(n):
    for c in range(m):
        if grid[r][c] == 0:
            zero.append([r, c])

return dfs(0)
```



---

**:thumbsup:dfs / bfs 模板** 

以Number of Islands為例
```python
# bfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.n, self.m = len(grid), len(grid[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = set()
        res = 0

        for r in range(self.n):
            for c in range(self.m):
                if grid[r][c] == "1" and (r, c) not in visited:
                    self.bfs(grid, r, c, visited)
                    res += 1
        return res

    def bfs(self, grid, r, c, visited): 
        q = deque()
        q.append((r, c))
        visited.add((r, c))
        while q:
            r, c = q.popleft()
            for dr, dc in self.dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < self.n and 0 <= nc < self.m and (nr, nc) not in visited and grid[nr][nc] == "1":
                    visited.add((nr, nc))
                    q.append((nr, nc))
        return 
```
```python
# dfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        res = 0
        self.n, self.m = len(grid), len(grid[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = set()

        for r in range(self.n):
            for c in range(self.m):
                if self.dfs(grid, r, c, visited):
                    res += 1
        return res 
    
    def dfs(self, grid, r, c, visited):
        if r < 0 or r >= self.n or c < 0 or c >= self.m or (r, c) in visited or grid[r][c] == "0":
            return False
        
        visited.add((r, c))
        
        for dr, dc in self.dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.n and 0 <= nc < self.m and (nr, nc) not in visited and grid[nr][nc] == "1":
                self.dfs(grid, nr, nc, visited)

        return True
```


---


* 會先把點連到的其他點放進stack並且pop出來，會最快連成一個完整路徑(先找children再找兄弟)

| ![](https://i.imgur.com/Ark6Tj0.png) | ![](https://i.imgur.com/FGKjlrw.png) |
| ------------------------------------ | ------------------------------------ |
| ![](https://i.imgur.com/dRJcAMn.png) | ![](https://i.imgur.com/OLoNljd.png) |
| ![](https://i.imgur.com/vwy9mCi.png) |![](https://i.imgur.com/4ZkCT2I.png) |


---




**講解連結**

Provided by. hard working me

*最近回看恆毅力這本書，裡面有一個公式，類似於 
天分 * 努力 = 技能
技能 * 努力 = 成就
我想我應該可以努力成為好的軟體工程師吧*

###### tags: `graph` `note` `code`