【AtCoder版！蟻本】ATC 001 A 深さ優先探索【深さ優先探索】

AtCoder版！蟻本の深さ優先探索で類題としてあげられているATC001 AをPythonで解いていきます。
深さ優先探索（DFS）は初めて見たとき難しく感じましたが、何問か解くとイメージがわいてきました。
理解しないと使いこなせないと思いますので頑張って取り組んでいきます。

リンク

atcoder.jp

AtCoder Typical Contest 001 A - 深さ優先探索

問題文

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

制約

・H(1≦H≦500)
・W(1≦W≦500)
・ci,j(0≦i≦H−1,0≦j≦W−1)
・i 行目 j 文字目の文字 ci,j はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
・s : その区画が家であることを表す。
・g : その区画が魚屋であることを表す。
・. : その区画が道であることを表す。
・# : その区画が塀であることを表す。
・高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
・与えられた街の外を通ることはできない。
・s と g はそれぞれ 1 つずつ与えられる。

解答例

# 深さ優先探索

from collections import deque

INF = int(1e9)

# 入力
h, w = map(int,input().split())
C = [] # 迷路の文字配列
for i in range(h):
    C.append(input())

# スタート、ゴールの探索
for y in range(h):
    for x in range(w):
        if C[y][x] == "s": # スタート座標はsx,sy
            sx = x
            sy = y
        if C[y][x] == "g": # ゴール座標はgx,gy
            gx = x
            gy = y

# 各座標への最短距離の配列（INFで初期化）
D = [[INF] * w for i in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# スタートからゴールへの最短距離を求める
def dfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    D[sy][sx] = 0 # スタート地点の距離を0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.pop() # 後入れのキューの要素を取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4): # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dx[i]
            nx = p[1] + dy[i]
            # 移動可能か、訪れたことがあるかの判定
            if 0 <= nx < w and 0 <= ny < h and C[ny][nx] != "#" and D[ny][nx] == INF:
                # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する
                que.append([ny,nx])
                D[ny][nx] = D[p[0]][p[1]] + 1
    return D[gy][gx]

res = dfs()
if res != INF:
    print("Yes")
else:
    print("No")

解説

スタート地点からゴール地点まで道を通ってたどり着けるか答える問題です。

深さ優先探索（DFS)で解いていきます。

Cに迷路の文字列を入れていき、スタート地点の座標sx,syとゴール地点の座標gx,gyを探索します。

迷路と同じ大きさの配列Dを用意しました。。
DはINFで初期化してあり、DFSでスタート地点からの最短距離を代入していきます。

DFSは最初スタート地点をキューにプッシュします。

キューからデータを取り出し、縦横4方向に移動させた座標nx,nyを求めました。
nx,nyが迷路の範囲内で その座標が道ならキューにプッシュし、最短距離も+1して更新します。

この作業をキューが空になるまで繰り返せば、通行できる道の最短距離がすべて更新されています。
ゴール地点のDが初期のINFのままなら到着できない と判断になるので、resの値にあわせて出力すればOKです。

こんな迷路問題を解けるようになりたい、っていうのが実は蟻本の購入動機のひとつでした。
意欲的に取り組んでいきます！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク