Pythonで幅優先探索(BFS)を実装してみる-ATC001&ABC151
本記事では、幅優先探索の基本的な最短経路を求める問題と少し応用的な問題を解いていきます。
幅優先探索(BFS)とは
幅優先探索(BFS)はBreadth First Searchの略で横型探索とも言われます。
その名の通り、幅を優先して探索していきます。といっても言葉だけではわかりにくいと思うのでどのように探索していくのか図をみてみましょう。
参照元:幅優先探索 - Wikipedia
グラフの深さを優先してひたすら掘り進めて探索していく深さ優先探索とは違い、幅を優先して探索していることがわかります。
nashidos.hatenablog.com
例題1
まずは深さ優先探索との違いを確認するために深さ優先探索の記事でも取り扱った問題を幅優先探索で解いていきます。
atcoder.jp
この問題は目的地までたどり着くことができるかどうかの判定なので深さ優先探索でも幅優先探索でも解くことができます。
実装
幅優先探索は深さ優先探索で利用したスタックをキューに交換することで実装することができます。
以下のコードが実際に実装したコードです。
import sys h,w = map(int,input().split()) C = [list(input()) for i in range(h)] visited = [[0 for i in range(w)] for i in range(h)] queue = [] for i in range(h): for j in range(w): if C[i][j] == 's': queue.append([i,j]) visited[i][j] = 1 dy_dx = [[1,0],[0,1],[-1,0],[0,-1]] while len(queue) > 0: now = queue.pop(0) if C[now[0]][now[1]] == 'g': print('Yes') sys.exit() for i in range(4): y = now[0]+dy_dx[i][0] x = now[1]+dy_dx[i][1] if 0 <= y < h and 0 <= x < w: if C[y][x] != '#' and visited[y][x] == 0: visited[y][x] = 1 queue.append([y,x]) print('No')
実際に深さ優先探索と幅優先探索でどのように探索の仕方が違うのか確認してみましょう。
入力
4 4 s... ..## .#.# .g..
深さ優先探索の場合
s... ..## .#.# .g.. -------------------- #... ..## .#.# .g.. -------------------- #... #.## .#.# .g.. -------------------- #... #.## ##.# .g.. -------------------- #... #.## ##.# #g.. -------------------- #... #.## ##.# #g.. -------------------- #... #.## ##.# #g.. -------------------- Yes
幅優先探索の場合
s#.. #.## .#.# .g.. -------------------- s#.. #### ##.# .g.. -------------------- s##. #### ##.# .g.. -------------------- s##. #### ##.# #g.. -------------------- s##. #### ##.# #g.. -------------------- s### #### ##.# #g.. -------------------- s### #### ##.# ##.. -------------------- s### #### ##.# ##.. -------------------- Yes
例題2
次は以下の問題を解いていきます。
atcoder.jp
実装
今回は最短経路を求めなければいけないので幅優先探索を使うべきでしょう。
また、スタートとゴールが決まっておらず、移動回数を求めるので先ほどよりかは少し応用的な幅優先探索の問題です。(と言ってもほとんど典型問題ですが…)
実装の方針としては、スタートの位置を全探索して最大の移動回数を求めていきます。
以下が実装したコードです。
h,w = map(int,input().split()) C = [list(input()) for i in range(h)] queue = [] visited = [] visited = [[0 for i in range(w)] for i in range(h)] ans = 0 for i in range(h): for j in range(w): if C[i][j] == '.': queue.append([i,j]) visited[i][j] = 1 dy_dx = [[1,0],[0,1],[-1,0],[0,-1]] while len(queue) > 0: now = queue.pop(0) for k in range(4): y = now[0]+dy_dx[k][0] x = now[1]+dy_dx[k][1] if 0 <= y < h and 0 <= x < w: if C[y][x] != '#' and visited[y][x] == 0: visited[y][x] = visited[now[0]][now[1]]+1 #移動回数のカウント queue.append([y,x]) for l in range(h): for m in range(w): ans = max(ans,visited[l][m]) queue = [] visited = [[0 for i in range(w)] for i in range(h)] print(ans-1)