前往
大廳
主題

從Leetcode學演算法跟python : DFS/BFS及python的deque

新手方 | 2022-07-16 16:19:42 | 巴幣 1004 | 人氣 951

# 前言

刷題是本魯的硬傷。為了不讓自己刷完就忘，在此練習透過巴哈小屋輸出。
目的是為了加固自己的印象，當然能幫助到其他人的話就更好了!

# 序

這個禮拜在研究一題 :
題目的大意是叫你找出一個有障礙物的平面空間中玩家是否能將箱子推到終點
若可以的話就回傳箱子移動最少次數，反之則回傳-1
這題有趣的地方在於要把推箱子的玩家納入考量，這點造就比一般的題目多的限制與解法

# 工具


說到路徑搜索，腦袋第一個要出現的就是DFS / BFS。這兩者算是路徑搜尋的暴力解法。

DFS (Deep-First Search)

顧名思義，是深度優先搜索。以箱子移動的方向來說，不考慮阻礙物的情況下，下一步可以往四個方向延伸。在挑了一個方向後，DFS會直接往前走下去，直到確定這條路不行為止，再回推至可能可以的"岔路"換一個方向走。
每次決定路線時，可以透過設定一個演算法改變方向，就能夠將DFS改造成A*等等的進階演算法
(wiki的圖，此處是展示每次第一個方向是往左邊的策略下DFS會如何走遍Tree。第一次碰壁(4)後就回朔至有路可走的3)
這個做法以實作來說是比較容易的，因為我們可以使用函式本身的特性以遞迴的方式實作
若不想用遞迴，可以使用迴圈搭配queue來做。

BFS (Breadth-First Search)

回過頭來說，BFS則是在選擇要往哪裡走時先把同一層的步數探索完之後再繼續往下進行的。
這種做法跟筆者玩遊戲探索地圖時比較相近
不然，往同一個方向深入後萬一因為劇情等等因素無法往回探就糟糕了!
實作上不能單用函式遞迴解決，必須搭配stack這個資料結構才行。

值得一提的是BFS的解一定是最速解，所以以這題的要求，很明顯地算箱子步數時要用BFS。

## Python實作 DFS/BFS

既然兩者都可以透過迴圈加上一個指定的資料結構解決，那此處就討論Python如何呼叫並使用stack跟queue。
以我這個不是拿Python當飯吃的人來說，只需要使用deque (發音deck) 資料結構就夠了。
# 建立deque
data = deque()
# 塞資料進去
data.append(somethingOne)
data.append(somethingTwo)
# 當作queue使用
data.popleft()
# 當作stack使用
data.pop()
一魚兩吃，且不爽哉
有了資料結構，就能實作兩種演算法了
不過實作時要注意題目提供的資料結構與限制，這部分每題都不同所以就不提供程式碼XD

# 解題思路


有了兩種演算法及兩者的優缺點後，我們就能夠來看看這題的需求
首先，題目要求箱子步數是最少的，所以就是用BFS無誤
但每次推箱子時也需要判斷玩家是否能到對應的位置，所以玩家這邊也需要BFS或是DFS
因為DFS實做容易且有很多減少判斷的變形 (ex : A*)，所以通常會用DFS或其變形

# 實做

這邊我不提供解答，但可以提供我看過好的網站給各位，讓各位參考:

上一篇
下一篇
#Leetcode#Python
留言

創作回應

廢物敗類窩囊廢漢堡
ㄐㄇ
2022-07-16 16:23:32
追蹤 創作集

作者相關創作

作品資料夾

相關創作

[LeetCode] 1424. Diagonal Travere II O(m*n)
1 131
[LeetCode]1814. Count Nice Pairs In an Array O(n^2) ~ O(n)
1 114
[LeetCode]1441. Build an Array With Stack Operations
1 111
[LeetCode] 501. Find Mode in Binary Search Tree - 二元樹追蹤
0 107
[LeetCode] 880. Decoded String at Index 逆向操作
1 162
[LeetCode] 1502. Can Make Arithmetic Progression From Sequence 荒漠甘泉TAT
3 191
[LeetCode] 24.Swap Nodes in Pairs
2 220
[LeetCode Python] 5. Longest Palindromic Substring— Dynamic Programming
3 851
[LeetCode C#] 121. Best Time to Buy and Sell Stock - Dynamic Programming, Maximum Subarray
0 576
[LeetCode C#] 111. Minimum Depth of Binary Tree - Binary tree, Breadth-First Search
0 452
[LeetCode C#] 108. Convert Sorted Array to Binary Search Tree - Binary Search Tree
1 544
[LeetCode C#] 101. Symmetric Tree - Binary tree, Depth-First Search
1 432
[LeetCode C#] 70. Climbing Stairs - Recursion With Memoization
0 680
[LeetCode C#] 2. Add Two Numbers - Linked List
0 722
[LeetCode C#] 35. Search Insert Position - Binary Search
0 310
[LeetCode C#] 26. Remove Duplicates from Sorted - Array
0 372
[LeetCode C#] 20. Valid Parentheses - Stack
0 470
[LeetCode C#] 13. Roman to Integer - Dictionary
0 411
數據分析學習心得及成果
3 17
Python 基本網頁爬蟲 - 下載圖片
0 33

更多創作

追蹤 創作集
其他創作
作品資料夾