概要
atcoderなどで幅優先探索の問題が出た際に、さらっと参照するための記事です。
細かな説明は、けんちょんさんの記事などを見た方が良いと思います。
というか、幅優先探索について初めて学ぶ方は、ぜひ上記の記事を先に読み、Pythonの実装部分だけ参考にしてもらえますと幸いです。
幅優先探索について
幅優先探索とは、グラフや木構造を探索するアルゴリズムで、探索を開始した点から近い順に探索していく方法です。
（対照的な方法として、深さ優先探索があり、こちらは行き止まりになるまで経路を戻らずに探索する方法です。）
イメージが非常にしやすいアルゴリズムなので、早速実装していきたいと思います。
画像引用元：Wikipedia
実装の方法
まず、グラフを隣接リスト(知らない方は@ellさんの記事などをお読み下さい。)などで受け取ります。
続いて、始点に隣接している頂点から順に探索していくのですが、ここで
- 頂点を探索したかどうかの管理
- 探索予定の頂点を格納する配列
の２点が重要になってきます。
１に関しては、管理できていないと同じ点を探索してしまうのでイメージがつきやすいかと思います。
2に関しては、配列などで見つけた順に格納し、先頭から要素を取り出すのが良いでしょう。
ここで、配列の先頭から要素を取り出すときに、通常の配列（pythonではlist）を用いると、操作１回に対して、配列の長さ分の処理が必要となってしまいます。
すなわち、長さNのlistに対して、先頭を取り出すpopに必要な計算量は$O(N)$となります。
これは、通常の配列の場合、先頭の要素を取り出すと、他の要素を一つずつずらす必要があることに起因します。
前置きが長くなってしまいましたが、この先頭の要素を取り出すのに適したものがキューというデータ構造です。
このキューを用いて、
- 探索予定の頂点を管理する
- 始点から順に探索をし、未探索の点があれば、キューに追加
を繰り返せば、幅優先探索が実装できます。
また、計算量はN個の頂点からM本の辺を調べる時、$O(N+M)$で表すことが出来ます。
それでは、実際に以下の問題を例にコードを見ていきましょう。
幅優先探索
問題概要
スタートからゴールまでの最短距離を出力する。
# キューをインポート
from collections import deque
# 入力を受け取る。座標の調整のため、スタート地点とゴール地点の座標を-1する。
R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sy -= 1
sx -= 1
gy -= 1
gx -= 1
# 迷路の情報を配列Gで受け取る
G = [input() for _ in range(R)]
# キューをQに入れ、スタート地点を追加
Q = deque()
Q.append([sy, sx])
# 未訪問と始点からの距離を管理するdistを定義。スタート地点に0を代入。
dist = [[-1]*C for _ in range(R)]
dist[sy][sx] = 0
# 今回は移動する４方向を事前に用意した。
dirc = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# キューの要素がなくなるまで処理を繰り返す。
while len(Q) > 0:
y, x = Q.popleft()
# 移動先で繰り返し処理
for dy, dx in dirc:
y2 = y + dy
x2 = x + dx
# 移動先が迷路の範囲内でなければ、continue
if not (0 <= y2 < R and 0 <= x2 < C):
continue
# 移動先が壁だったら、continue
if G[y2][x2] == "#":
continue
# 移動先が未訪問なら移動前の距離＋１をdistに入れて、キューに移動先の座標を追加
if dist[y2][x2] == -1:
dist[y2][x2] = dist[y][x] + 1
Q.append([y2, x2])
# ゴールの距離を出力
print(dist[gy][gx])
終わりに
幅優先探索は、問題での活用はもちろん、このアルゴリズムを応用したものが多々出題されています。
ぜひ、この記事を読んだ後に他の方の解説記事や、@e869120さんが書かれた分野別 初中級者が解くべき過去問精選 100 問などで練習問題をこなし、活用の幅を広げてみてください。
ここまで、お読みいただきありがとうございました。