BFS(幅優先探索)ってなに？

皆さん、こんにちは！

ハリーです！競プロ精進日記の1週目になります。何から勉強を始めようか悩んだのですが、今週は、以前やろうと思ってやれていなかった BFS(幅優先探索) の勉強をしたいと思います。今回、BFS のアルゴリズムについて書こうと思ったのですが、私自身あまり理解していないことと、BFS についての解説記事が他にたくさんあったので今回は問題を解いていく過程記事に書かせていただきました。今回、BFS の問題を解いていくにあたって AtCoder Tags を使用させていただきました。このサイトでは、AtCoder の問題をカテゴリ別に分類してくれており、自分がやりたいカテゴリの問題を簡単に探すことが出来ます！もし、知らない方がいましたら是非使ってみてください！今回の記事は完全に自分のためのメモみたいになってます...。

C - 幅優先探索（AtCoder Beginner Contest 007）
問題の概要
実装方法
ACコード
最後に

C - 幅優先探索（AtCoder Beginner Contest 007）

　1つ目の問題は、C - 幅優先探索という問題です。選択した理由は、問題の名前の通り BFS の基本となる問題だと思ったからです！それでは、解いていきましょう！

問題の概要

盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられます。
それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられます。
タート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着けるようになっています。

　スタート地点からゴール地点に移動する最小手数を $1$ 行に出力する問題です。

　最後に改行を忘れないこと！

入力例1

7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

出力例1

入力例2

5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########

出力例2

入力例3

50 50
2 2
49 49
##################################################
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
##################################################

出力例3

実装方法

まず問題文にも記載がありますが、幅優先探索ではキューというデータ構造を用いて以下の2つを行います。

追加(Push): キューの末尾にデータを追加する。
取り出し(Pop): キューの先頭のデータを取り出す。

上記の2つを行うために、collections ライブラリのimport を行います。

　from collections import deque

次に入力を受け取ります。

まず、1行目で行数 $R(1\leq R \leq 50)$と列数 $C(1\leq C \leq 50)$を受け取ります。

 r, c = map(int,input().split())

2行目でスタート地点の座標$(sy, sx)$、3行目でゴール地点の座標$(gy, gx)$を受け取ります。

 sy, sx = map(int,input().split())
 gy, gx = map(int,input().split())

4行目で $R$ 行、長さ $C$ の文字列を1行ずつ受け取ります。

 grid = [list(input()) for _ in range(r)]

5行目以降で、盤面の情報を受け取ります。

 grid = [list(input()) for _ in range(r)]

次に、受け取った座標のindex値をそろえるために、座標の値を$-1$します。

 (sy, sx, gy, gx) = (sy - 1, sx - 1, gy - 1, gx - 1)

距離を保存するための配列を用意します。初期値として、各要素に $-1$ を入れます。

なぜ $-1$ を入れるかというと、距離が正の数であるため負の数で入れておくとまだ訪れていないことが表せるためです。

dist = [[-1] * c for _ in range(r)]

スタート地点はスタート地点から手数 $0$ でたどり着けるので、最短手数の $0$ を入れます。

 dist[sy][sx] = 0

次は壁の判定を行います。# がある場合は、壁があるということなので壁用の値の $-2$ を入れます。

 for i in range(r):
   for j in range(c):
       if grid[i][j] == "#":
           dist[i][j] = -2

deque オブジェクトを生成します。生成したらスタート地点の座標を加えます。

 q = deque()
 q.append([sy, sx])

上下左右に対する変化量を決めます。

 d = [[-1, 0], [1, 0], [0, -1], [0, 1]]

ここからが、BFS の主な処理になります。

まず while 文を作ります。while 文の中で初めにやるのが今いる地点の保存です。

 v = q.popleft() 

次に、今いる地点から上下左右を見ます。これは for 文で処理を行います。

 for dy, dx in d:

次は、今いる地点から上下左右を見たときの地点が範囲内であるかどうかを if 文で調べます。範囲外だった場合は、無視して何も処理を行いません。

 if not (0 <= v[0] + dy <= r - 1 and 0 <= v[1] + dx <= c - 1):
            continue

次に、今いる地点から上下左右を見たときにその地点が訪れたことのある地点かどうかを if 文で調べます。各配列要素に初期値として $-1$ を入れているので、$-1$ ではなかった場合、その地点は1度訪れたことがある、または壁があるということになるので、無視して処理を行いません。

 if dist[v[0] + dy][v[1] + dx] != -1:
            continue

次に、距離の更新を行います。上記の2つの条件分岐を通過した場合、その地点は進むことができるということなので、今いる地点に $+1$ をして距離を更新してあげます。

 dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1

while 文の最後で、上記の条件分岐で訪れることができる地点がある場合は、新しい地点としてキューに追加してあげなければいけないので append で次の地点を配列 q に追加します。

 q.append([v[0] + dy, v[1] + dx])

最後は、距離を保存した配列（dist）のゴール地点を出力すれば最小手数を出すことができます。

 print(dist[gy][gx])

今までのコードをまとめると下記のようになります。

ACコード

　from collections import deque

　r, c = map(int,input().split())
　sy, sx = map(int,input().split())
　gy, gx = map(int,input().split())
　grid = [list(input()) for _ in range(r)]
 
　(sy, sx, gy, gx) = (sy - 1, sx - 1, gy - 1, gx - 1) # 0index
　dist = [[-1] * c for _ in range(r)] #　距離を保存するための配列
　dist[sy][sx] = 0 # スタート地点は０
 
　# 壁の判定（distに壁用の数値を入れている）
　for i in range(r):
　    for j in range(c):
　        if grid[i][j] == "#":
　            dist[i][j] = -2
 
　q = deque()
　q.append([sy, sx]) # スタート地点
　 
　d = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 上下左右に対する変化量(y, x)
 
　while q:
　    v = q.popleft() # 今いる場所(y, x)
　    for dy, dx in d: # 現在の地点から上下左右を見ている
     　   if not (0 <= v[0] + dy <= r - 1 and 0 <= v[1] + dx <= c - 1): # 範囲外と壁は行かない
　            continue # 配列外参照
     　   if dist[v[0] + dy][v[1] + dx] != -1: # 訪れたことがあるか壁の時は無視する
         　   continue
      　  dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1 # 距離の更新
   　     q.append([v[0] + dy, v[1] + dx]) # 新しくキューに追加する    
 
　print(dist[gy][gx])

最後に

　以上が競プロ精進日記の1週目はBFS(幅優先探索) の練習記事でした！問題文が既に解説のような感じでしたね。BFS をやり始めた私にとっては、すごくためになる問題でした。さて、そろそろ今年も終わろうとしていますね。皆さんは今年どんな1年だったでしょうか？私は、単位に追われた1年でした...笑　後は夏のインターンシップで HTML と CSS に興味が湧いたので、今勉強中です！来年の春には入茶できるように頑張ります！

最後まで読んでいただいきありがとうございました！

Harryのブログ

競プロ初心者によるブログです