幅優先探索(BFS)を学ぶ

同期が幅優先探索の勉強会を開いてくれたので、覚えられるように書いときます。

幅優先探索とは、グラフ探索の一解法だそうです
他にも深さ優先探索（DFS）があるそうです

以下参考文献
https://qiita.com/drken/items/996d80bcae64649a6580

んで、今回実装した例
理解のためにいろいろコメントを入れてます

# 今回、dequeというモジュールを使用、キューだけでなくスタックチックな用途にも使える
from collections import deque

# 入力をすべて受ける
r, c = map(int, input().split())
sy, sx = map(int, input().split()) # START
gy, gx = map(int, input().split()) # GORL

# マス目と数と合わせるためにすべて引く、
sy -= 1
sx -= 1
gy -= 1
gx -= 1

# 今回この書き方で値取得できるの知れたのがよかった
grid = [input() for _ in range(r)]

# print(grid)
# dequeの宣言は以下、初期値を入れる
q = deque()
q.append((sy, sx))

# 距離の情報を保持するdistを作成、スタート地点には0を入れる
INF = -1 #1<<60 # 2: 0001 1<<3: 1000
dist = [[INF for _ in range(c)] for __ in range(r)]
dist[sy][sx] = 0

# 下に行くとY、正　右にいくとX、正
# ↓→↑←を文字列に置き換えた
dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

# キューがなくなるまで続ける
while(len(q) > 0):

    # 左側から取り出してnowに入れる、現在の座標がy, xに入る
    now = q.popleft()
    y, x = now

    # ↓→↑←それぞれに対して、一つずつ動かした後の座標を入れる
    for di in range(4):
        ny = y + dy[di]
        nx = x + dx[di]
        
        # 更新後の座標が枠をはみ出る、0より小さくなったら何もしない
        if (ny<0 or ny>=r or nx<0 or nx>=c): continue
        # 更新後の座標に#があったら何もしない
        if (grid[ny][nx] == '#'): continue
        # 更新後の座標に何かしら値が入ってたら何もしない（更新しない）
        if (dist[ny][nx] != INF): continue
        
        # 距離の更新、現在の距離に+1をする
        dist[ny][nx] = dist[y][x] + 1
        # 更新後の座標を新たにキューに入れる
        q.append((ny, nx))

# これは、whileループをこなすごとにキューにどんどん値が入ってくるが、
# それらには値が一度でも入れば更新されず、やがてはすべての範囲を調べつくすので
# 値が入りきったら終わり、ということか

# for i in range(r):
#     for j in range(c): print(dist[i][j], end='')
#     print()

print(dist[gy][gx])

なるほど、、、奥が深いなぁ
これを自分で実装するのはなかなかにハードルが高いが、
類似問題を色々やってみようと思う

以上