アルゴリズム力UP!『ATC 001 A 幅優先探索 』を解いてみよう

記事を読むとわかること

• 記事の作者の『ATC 001 A 幅優先探索 』の解法がわかる
• 記事の作者のアルゴリズム問題全般へのアプローチがわかる

今回の問題

ATC 001 A 幅優先探索　→ 問題文はこちら

記事の作者の回答のコード

from collections import deque

# ==============================================================
# return: スタートのマスを代入すると、スタートからゴールまでの最短手数を出力
# pre, post: 問題文に記載 -> 2 3 のマスの解釈を 3行目の2列目にあるマス というのではなく、2次元配列の2行目の3行目にあるマス　と最初考えた方が混乱しないかも。

# ==============================================================
# ★ step1 問題文を解くために必要な迷路をインプットする
# ★ step2 幅優先探索でスタートからゴールにむかい上下左右に探索をさせる。
# ★ step3 探索を進む際に、これから進むマス = 前回進んだマスのスタートからの手数 + 1 をし、マーキングをする。
# ★ step4 ゴールにたどり着いた際、ゴールのマス時点でのスタートからの手数を返す


#問題分の行と列の数をインプット
r, c = map(int, input().split())
#スタートのマスの場所をインプット
sx, sy = map(int, input().split())
#ゴールのマスの場所をインプット
gx, gy = map(int, input().split())
sy -= 1
sx -= 1
gx -= 1
gy -= 1
#r個分ある迷路の描画を一列ずつインプット
maze = [list(input()) for i in range(r)]


#幅優先探索
def bfs():
    # 上下左右の4方向に分岐させる (今回は1行目の0行目みたいな解釈になるので、どの方向かは厳格に考えない方が無難？)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #探索をする際にスタートからの手数を記憶するために、別で新たに迷路と同じ大きさのモノを用意。
    d = [[float("inf")] * c for i in range(r)]
    #キューの作成
    que = deque([])
    #スタートのマスをいれる
    que.append((sx, sy))
    #スタートを0とする(今後マスを進めるたびに加算していく。)
    d[sx][sy] = 0
    
    while que:
        #先入先出しで四方向に順番に検索していく
        p = que.popleft() 
        #popしたものがゴールか判断
        if p[0] == gx and p[1] == gy:
            break
        #四方向の指定
        for i in range(4):
            #四方向にすすむ     
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            #指定いる座標が迷路内か判定
            if 0 <= nx < r and 0 <= ny < c :
                #指定した座標が塀ではないか判定
                if maze[nx][ny] != "#" :
                    #指定した座標が未開拓であることを判定
                    if d[nx][ny] == float("inf"):
                        que.append((nx, ny))
                        #新しく開拓する場所に、既に開拓した場所の値を+1し代入させる
                        d[nx][ny] = d[p[0]][p[1]] + 1
    #popした際の進んだ値を返す
    return d[gx][gy]

print(bfs())

回答の解説

記事の作者が思う今回のアルゴリズム問題の回答ポイント

• 迷路やスタート及びゴールを入力する際、迷路が配列で扱う関係で０番目スタートであることを意識
• 幅優先探索であるため、先入先出しのためのpopleftメソッドを使う
• 条件分岐として、迷路の範囲内か、塀か、未探索かを判断する
• 探索先に前回探索した時のスタートからの手数+1をする

#このコードの課題感

• 今回の前提として〜行目の〜行目のマスとしたが、仮に「2行２列目」がスタートであると解釈する場合、今回の変数x(列),y(行)がちょっと気持ちが悪くなる