Qiitaに登録したものの、ろくに活用していなかったので使ってみます。

この記事の目的

・自分用のメモ
・以前Pythonの幅優先探索の記事を探したら見つからなかったので、同じような初心者むけに公開したい
・ここに書いたらもっと良い書き方を誰かが教えてくれるかもしれない

結論

・連結で、辺の長さがないグラフの直径は幅優先探索（BFS）で求められる
・リストの先頭から要素を取り出す操作は遅い
・ただしdequeを使うと少し改善される

解く問題と、解答の方針

問題

ABC151 D - Maze Master

これを解きます。（ABCのD問題にはたまにグラフの問題が出題されます。）
問題文はリンク先で確認してください。

解答の方針

グラフの問題と解釈します。
マスを頂点として上下左右に隣接する頂点を辺で結べば、迷路は連結なグラフで表されます。したがってこの問題は「連結で辺の長さがないグラフの直径を求める問題」と考えられます。
ここで直径とは頂点間の距離の最大値です。

幅優先探索（BFS）とは

詳しくは他の記事を見ていただきたいのですが、幅優先探索とはある頂点(startとする）から到達可能な場所を求めるためのアルゴリズムです。

今回はこれを応用して
頂点(start)からの距離の最大値を求める操作を行います。
まず各頂点につながる辺のリスト(edge)を用意して、あとは以下のフローチャートに従って、用意したリスト(distance)にstartからの距離を記入していきます。

このフローチャートに赤文字で書いてある「先頭から」という部分を「末尾から」に変えると、深さ優先探索（DFS）になります。
ただしグラフの直径はDFSでは求められません。

幅優先探索では、到達可能になった頂点にすぐ移動するため、遠回りが生じません。したがって最短距離を求めることができます。
もちろん、辺に長さがある場合には別です。

最後に、この操作をグラフの全頂点で行って、得られた値のうち最大のものを出力すれば終了です。


H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
 
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='#':
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      edge[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      edge[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      edge[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      edge[n].add(n+1)
    n+=1

def dfs(start):
  reach=[start]
  distance=[-1 for _ in range(H*W)]
  distance[n]=0
  while reach:
    _from=reach.pop(0)
    for _to in edge[_from]:
      if not(_to in reach) and distance[_to]==-1:
        reach.append(_to)
        distance[_to]=distance[_from]+1
  return(max(distance))
 
n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

これでACできました。

リストの先頭を取り出すのは遅い

基本的にはこれでいいのですが・・・
pythonはけっこう速度が遅く、気を付けないとすぐTLEになります。
時間のかかる操作はできるだけ減らしたほうがいいです。
たとえば、リストの先頭から要素を取り出す操作はとても遅いです。

import time
list_1=[i for i in range(100000)]
list_2=[i for i in range(100000)]

# 先頭から要素を取り出す
start_1=time.time()
while list_1:
  x=list_1.pop(0)
end_1=time.time()

# 末尾から要素を取り出す
start_2=time.time()
while list_2:
  x=list_2.pop(-1)
end_2=time.time()

print('先頭から：{}'.format(end_1-start_1))
 #=>先頭から：1.4942412376403809
print('末尾から：{}'.format(end_2-start_2))
 #=>末尾から：0.014818668365478516

同じ操作をしているのに、先頭から要素を取り出したとき100倍くらいの時間がかかっています。
今回は大丈夫でしたが、同様の操作がたくさん続くときには対策をしたほうがいい気がします。

dequeを使う

リストの先頭から要素を取り出すときは、deque（両側キュー）という型が便利です。
詳しくはここを見てください。
collections --- コンテナデータ型（Python 3.7.3 ドキュメント）

ざっくりいうと
・配列の先頭、あるいは末尾から要素をとりだすときはdequeが速い
・中央から取り出すときはlistが速い
という感じのようです。

import time
from collections import deque

list_1=[i for i in range(100000)]
deq=deque([i for i in range(100000)])

# listで先頭から出す
start_1=time.time()
while list_1:
  x=list_1.pop(0)
end_1=time.time()

# dequeで先頭から出す
start_3=time.time()
while deq:
  x=deq.popleft()
end_3=time.time()

print('list：{}'.format(end_1-start_1))
 #=>list：1.4939298629760742
print('deque：{}'.format(end_3-start_3))
 #=>deque：0.009586334228515625

非常に早く終わりました。
今回の問題はリストの長さが400くらいなのであまり差が生じませんが（むしろ遅い）、長くなるほど恩恵にあずかれそうです。
dequeを使った解答は以下です。


from collections import deque
 
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
 
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='#':
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      edge[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      edge[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      edge[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      edge[n].add(n+1)
    n+=1

def dfs(start):
  reach=deque([start])                               #この行が変化
  distance=[-1 for _ in range(H*W)]
  distance[n]=0
  while reach:
    _from=reach.popleft()                            #この行が変化
    for _to in edge[_from]:
      if not(_to in reach) and distance[_to]==-1:
        reach.append(_to)
        distance[_to]=distance[_from]+1
  return(max(distance))
 
n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

まとめ

今回はBFSの覚えがきをしました。直径をBFSで求められるというのは、正直この問題を解くまで認識していませんでした。
他のグラフの問題も解いてみて、暇ができれば投稿したいと思います。