【Python】深さ優先探索と幅優先探索

アルゴリズムの勉強をしていてよくわからなかった２つの違いが(なんとなく)わかったので説明してみることにしました。
今回はそれぞれスタックとキューというデータ構造を使った方法を用います。再帰は扱いません。

深さ優先探索とは

深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。
ウィキペディアより

イメージ

迷路の深いところから優先して探索し行き止まりになったら戻りながらまだ訪れていない場所に向かおうとします。

幅優先探索とは

幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。
幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
ウィキペディアより

イメージ

今いる場所のお隣を全て探索したら次に進みます。深さではなく幅を優先していますね。

stack構造を使ったDFS(深さ優先探索)

stackとは

後入れ先出し LIFO（Last In First Out）
本を積んでいきそれらを上から順に取っていくイメージ。（後から置いた本の方を先に取り出している。）

例題 ATC001 Aより
問題文
高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。
高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

#=== 標準入力と使用するデータの整理 ===#
h, w = map(int, input().split())
sx, sy, gx, gy = None, None, None, None
town = []
edge = ['#'] * (w+2) # 上下を塀で囲む
for i in range(h):
    line = list(input())
    line = ['#'] + line + ['#'] # 左右を塀で囲む
    for j in range(w+2):
        if line[j] == 's':
            sx, sy = j, i+1 # スタート座標
    for j in range(w+2):
        if line[j] == 'g':
            gx, gy = j, i+1 # ゴール座標
    town.append(line)
town = [edge] + town + [edge] #この問題でいうところの街の地図
visited = [[False]*(w+2) for _ in range(h+2)] #街のどこに訪れたかを記録する

#=== 深さ優先探索　開始 ===#
stack = [[sx, sy]] # スタックにスタート地点の座標を入れる
visited[sy][sx] = True # スタート地点を"訪問済み"にする
while stack: # stackの中身がある間
    x, y = stack.pop()
    if town[y][x] == 'g':
        print('Yes')
        exit() # 現在地点がゴールであれば'Yes'と出力して実行を終了する
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] # 次に訪れる場所　左上右下
    for dx, dy in hjkl:
        if (dx<1) or (dx>w+1) or (dy<1) or (dy>h+1) or town[dy][dx] == '#' or visited[dy][dx] is True:
            # 進行方向が塀、街の範囲外、もしくは訪問済みであればスキップ
            continue
        # そうでなければその進行方向を新しくスタックに積み、訪問済みにする
        stack.append([dx, dy])
        visited[dy][dx] = True

print('No') # たどり着けなかった時は'No'と出力する

queue構造を使ったBFS(幅優先探索)

queueとは

先入れ先出し FIFO（First In First Out）
レジに並んでいる人たちが先に並んだ人から処理されていくイメージ(先入れ先出し)

例題 ABC007 Cより
問題文
たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。
まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。
今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。どうやって求めるかを調べていたところ、「幅優先探索」という手法が効率的であることを知りました。 (一部略)

#=== 標準入力と使用するデータの整理 ===#
r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = [i-1 for i in [sx, sy, gx, gy]] # 座標をindexに修正
maiz = []
for _ in range(r):
    line = list(input())
    maiz.append(line)

#=== 幅優先探索　開始 ===#
queue = [[sx, sy]] # スタート地点をキューに入れる
maiz[sy][sx] = 0 # 手数０からスタート
visited = [[False]*c for _ in range(r)] # 訪問したかどうかをメモする
while queue:
    x, y = queue.pop(0)
    visited[y][x] = True # 訪問済みにする
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] # 次に訪れる場所　左上右下
    for dx, dy in hjkl:
        if (maiz[dy][dx] == '.') and (visited[dy][dx] is False):
            # 進行可能でまだ訪問していなければキューに入れてかかった手数を記録する
            queue.append([dx, dy])
            maiz[dy][dx] = maiz[y][x]+1

print(maiz[gy][gx]) # ゴール地点に記録された手数を参照

疑問点：　進行方向の順番　斜め方向　について

進行方向の順番

４方向だと全部で24通りの順番がありますが進行方向の順番は多分なんでも良いです。（この順番で進むとダメってパターンがあったら教えていただきたいです。）

斜め方向

進めます。問題によっては斜め方向に進んでもよいという条件があるので柔軟に対応しましょう。
AOJ 1160 島はいくつある？