記事を読むとわかること
- 記事の作者の『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(行)がちょっと気持ちが悪くなる