# **程式筆記(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走不通時，要把走過的路徑清乾淨
```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中累積
```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統計
```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是最小值
```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再找兄弟)
|  |  |
| ------------------------------------ | ------------------------------------ |
|  |  |
|  | |
---
**講解連結**
Provided by. hard working me
*最近回看恆毅力這本書，裡面有一個公式，類似於
天分 * 努力 = 技能
技能 * 努力 = 成就
我想我應該可以努力成為好的軟體工程師吧*
###### tags: `graph` `note` `code`
Sign in with Wallet
Connect another wallet