Pythonで深さ優先探索(DFS)を実装してみる-ATC001
本記事では、深さ優先探索をPythonを利用して実装していきます。
実際に深さ優先探索の典型問題をスタックと再帰関数の2パターンの解き方で実装し、解説していきます。
深さ優先探索(DFS)とは
深さ優先探索とはDepth First Searchの略で、バックトラック法とも言われます。
目的のノードを見つけるか、全て探索し終わるまで1と2を繰り返します。
- 目的のノードをみつけるか、探索できる子ノードがなくなるまで探索
- 探索できる子ノードがなくなるとバックトラック（分岐したところまで戻る）して、再び探索
探索していく順序は以下の通りです。
途中で分岐できる場合でも気にせず深くまで探索するので深さ優先探索と呼ばれます。←ここが幅優先探索との違い！
幅優先探索の記事はこちら↓
nashidos.hatenablog.com
例題
今回は以下の問題を扱います。
atcoder.jp
問題文
高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。
高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。
再帰関数で実装
まずは再帰関数を利用して解いていきたいと思います。
実装の方針としては、深さ優先探索なのでまず最初にできるだけ深く探索します。
そして、探索できなくなると別の方向に探索を始めます。
この流れを再帰関数を利用して実装したのが以下のコードです。
import sys sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限 h,w = map(int,input().split()) c = [list(input()) for i in range(h)] def dfs(x,y): if not(0 <= x < h) or not(0 <= y < w) or c[x][y] == "#": # 壁に当たったり、探索範囲外になった場合はreturn return if c[x][y] == "g": # ゴールを見つけたら”Yes”を出力して終了 print("Yes") sys.exit() c[x][y] = "#" #探索済みを示すためのマーキング dfs(x+1,y) dfs(x-1,y) dfs(x,y+1) dfs(x,y-1) for i in range(h): for j in range(w): if c[i][j] == "s": sx, sy = i, j # スタート位置 dfs(sx, sy) print("No")
コードだけみてもよくわからないかもしれないので、実際にどのように探索しているのか見てみましょう。
入力
4 4 s... ..## .#.# .g..
探索プロセス
s... ..## .#.# .g.. -------------------- #... ..## .#.# .g.. -------------------- #... #.## .#.# .g.. -------------------- #... #.## ##.# .g.. -------------------- #... #.## ##.# #g.. -------------------- #... #.## ##.# #g.. -------------------- #... #.## ##.# #g.. -------------------- Yes
深さを優先して探索していることがわりますね。
それでは、次はスタックで実装していきます。
スタックで実装
スタックで実装する場合も先ほどと方針は変わりません。
変更する点として、探索する位置をスタックを利用して管理します。
以下がスタックを利用して実装したコードです。
import sys h,w = map(int,input().split()) c = [list(input()) for i in range(h)] for i in range(h): for j in range(w): if c[i][j] == "s": sx,sy = i,j #スタート elif c[i][j] == "g": gx,gy = i,j #ゴール stack = [[sx,sy]] visited = [[0 for i in range(w)]for j in range(h)] visited[sx][sy] = 1 dx_dy = [[1,0],[0,1],[-1,0],[0,-1]] while stack: x,y = stack.pop() #要素を取り出す for i in range(4): nx,ny = x+dx_dy[i][0], y+dx_dy[i][1] #現在の位置 if 0 <= nx < h and 0 <= ny < w and visited[nx][ny] == 0 and c[nx][ny] != '#': visited[nx][ny] = 1 #訪れた印をつける stack.append([nx,ny]) #スタックに現在位置をpush if visited[gx][gy] == 1: print("Yes") sys.exit() print("No")
再帰関数のコードよりも量が多く少し複雑になった気がします…
