nashidos’s diary

アルゴリズムとか機械学習とか色々

Pythonで幅優先探索(BFS)を実装してみる-ATC001&ABC151

今回は幅優先探索Pythonで実装していきます。

本記事では、幅優先探索の基本的な最短経路を求める問題と少し応用的な問題を解いていきます。

幅優先探索(BFS)とは

幅優先探索(BFS)はBreadth First Searchの略で横型探索とも言われます。

その名の通り、幅を優先して探索していきます。といっても言葉だけではわかりにくいと思うのでどのように探索していくのか図をみてみましょう。
幅優先探索の探索順序
参照元幅優先探索 - Wikipedia

グラフの深さを優先してひたすら掘り進めて探索していく深さ優先探索とは違い、幅を優先して探索していることがわかります。
nashidos.hatenablog.com


例題1

まずは深さ優先探索との違いを確認するために深さ優先探索の記事でも取り扱った問題を幅優先探索で解いていきます。
atcoder.jp
この問題は目的地までたどり着くことができるかどうかの判定なので深さ優先探索でも幅優先探索でも解くことができます。

実装

幅優先探索深さ優先探索で利用したスタックをキューに交換することで実装することができます。

以下のコードが実際に実装したコードです。

import sys
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]
visited = [[0 for i in range(w)] for i in range(h)]
queue = []

for i in range(h):
    for j in range(w):
        if C[i][j] == 's':
            queue.append([i,j])
            visited[i][j] = 1
            
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

while len(queue) > 0:
    now = queue.pop(0)
    if C[now[0]][now[1]] == 'g':
        print('Yes')
        sys.exit()
    for i in range(4):
        y = now[0]+dy_dx[i][0]
        x = now[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if C[y][x] != '#' and visited[y][x] == 0:
                visited[y][x] = 1
                queue.append([y,x])
                
print('No')

実際に深さ優先探索幅優先探索でどのように探索の仕方が違うのか確認してみましょう。

入力

4 4
s...
..##
.#.#
.g..

深さ優先探索の場合

s...
..##
.#.#
.g..
--------------------
#...
..##
.#.#
.g..
--------------------
#...
#.##
.#.#
.g..
--------------------
#...
#.##
##.#
.g..
--------------------
#...
#.##
##.#
#g..
--------------------
#...
#.##
##.#
#g..
--------------------
#...
#.##
##.#
#g..
--------------------
Yes

幅優先探索の場合

s#..
#.##
.#.#
.g..
--------------------
s#..
####
##.#
.g..
--------------------
s##.
####
##.#
.g..
--------------------
s##.
####
##.#
#g..
--------------------
s##.
####
##.#
#g..
--------------------
s###
####
##.#
#g..
--------------------
s###
####
##.#
##..
--------------------
s###
####
##.#
##..
--------------------
Yes

深さ優先探索は深さを優先して、幅優先探索は幅を優先していることがわかりますね。

例題2

次は以下の問題を解いていきます。
atcoder.jp

実装

今回は最短経路を求めなければいけないので幅優先探索を使うべきでしょう。

また、スタートとゴールが決まっておらず、移動回数を求めるので先ほどよりかは少し応用的な幅優先探索の問題です。(と言ってもほとんど典型問題ですが…)

実装の方針としては、スタートの位置を全探索して最大の移動回数を求めていきます。

以下が実装したコードです。

h,w = map(int,input().split())
C = [list(input()) for i in range(h)]

queue = []
visited = [] 
visited = [[0 for i in range(w)] for i in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            while len(queue) > 0:
                now = queue.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if C[y][x] != '#' and visited[y][x] == 0:
                            visited[y][x] = visited[now[0]][now[1]]+1 #移動回数のカウント
                            queue.append([y,x])
                    
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])
            
        queue = []
        visited = [[0 for i in range(w)] for i in range(h)]              
        
print(ans-1)

まとめ

幅優先探索は幅を優先して探索!

最短経路問題を解く時には幅優先探索

おわり。