【AtCoder】Pythonで使いこなす深さ優先探索・幅優先探索

はじめに
深さ優先探索とは
1. 典型的な問題とサンプルコード
幅優先探索とは
1. 典型的な問題とサンプルコード
深さ優先探索と幅優先探索
参考

はじめに

深さ優先探索と幅優先探索について、どんなものなのか、典型的な問題とそのサンプルコードを紹介したいと思います。

深さ優先探索と幅優先探索の実装については、問題ごとに実装を変える必要があるので注意してください。

今回扱う問題は、AtCoderのAtCoder Typical Contestからサンプル問題を選びました。

深さ優先探索とは

深さ優先探索(DFS: Depth-First Search)とは、深さ（それ以上の状態に繊維できないまで）を優先的に探索する手法です。

初期状態から遷移し、それ以上遷移できなくなったら、1つ前の状態に戻り、さらに探索していない状態へ遷移することを繰り返します。

状態の遷移を木構造で考えると深さを優先していることがわかりやすいです。最初の状態（根）から深さ方向に探索していき、状態の遷移を繰り返すことで全ての状態を列挙できます。

典型的な問題とサンプルコード

A - 深さ優先探索

AtCoderisaprogrammingcontestsiteforanyonefrombeginnerstoexperts.Weholdweeklyprogrammingcontestsonline.

スタートからゴールまで辿り着けるかを判定する問題です。

スタートから辿り着ける場所を全て列挙して、その中にゴールがあるか確認すればいいので、深さ優先探索でスタートから探索してゴールに辿り着けるか判定します。

深さ優先探索は再起関数で簡単に書けます。

Pythonでは再起呼び出しの上限があり、デフォルトでは1000になっています。AtCoderのテストケースでは足りないので、上限の設定をしておく必要があります。

>>> import sys
>>> sys.getrecursionlimit()
1000

import sys
sys.setrecursionlimit(10**7) # 再起回数の設定

H, W = map(int, input().split())
maze = [list(input()) for h in range(H)]

for h in range(H):
    for w in range(W):
        if maze[h][w] == "s":
            sx, sy = h, w

# 深さ優先探索
def dfs(x, y):
    # 範囲外や壁の場合は終了
    if y >= W or y < 0 or x >= H or x < 0 or maze[x][y] == '#':
        return

    # ゴールに辿り着ければ終了
    if maze[x][y] == 'g':
        print('Yes')
        exit()

    maze[x][y] = '#' # 確認したルートは壁にしておく

    # 上下左右への移動パターンで再起していく
    dfs(x+1, y)
    dfs(x-1, y)
    dfs(x, y+1)
    dfs(x, y-1)

dfs(sx, sy) # スタート位置から深さ優先探索
print('No')

幅優先探索とは

幅優先探索(BFS: Breadth-First Search)とは、幅（最初の状態から近い状態）を優先的に探索する手法です。

最初の状態から1回の遷移でいける全ての状態、2回の遷移でいける全ての状態と繰り返して全ての状態を列挙できます。

木構造で考えると同じ深さにあるノードを根に近い方から探索するというイメージになります。
根に近い方から探索するため、最短経路や最小手数などの問題も求めることができます。

典型的な問題とサンプルコード

A - 幅優先探索

AtCoderisaprogrammingcontestsiteforanyonefrombeginnerstoexperts.Weholdweeklyprogrammingcontestsonline.

迷路でのスタートからゴールの最小移動手数を求める問題です。

スタートから1回で辿り着けるマス、2回で辿り着けるマス...と全てのマスに対してスタートから最短手数で辿り着ける数を求めながら最終的にゴールのマスの最小手数を求めます。

再入れ先出しのキューというデータ構造を使うと実装が簡単です。
Pythonではdepue（両端キュー）を利用します。

from collections import deque

R, C = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
maze = [list(input()) for h in range(R)]

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

dist = [[10**4 for i in range(C)] for j in range(R)] # 各マスの最小手数

for r in range(R):
    for c in range(C):
        if maze[r][c] == '#':
            dist[r][c] = -1 # 壁は-1

dist[sx][sy] = 0

que = deque()
que.append([sx, sy])
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 移動方向のリスト

# 幅優先探索
while que:
    x, y = que.popleft() # キューから取り出し

    # 現在位置から上下左右に探索
    for i, j in d:
        if x+i >= R or x+i < 0 or y+j >= C or y+j < 0: # 範囲外
            continue
        if maze[x+i][y+j] == '#': # 壁
            continue
        if dist[x+i][y+j] != 10**4: # すでに最小手数確定済み
            continue

        dist[x+i][y+j] = dist[x][y] + 1

        que.append([x+i, y+j]) # 次のマスをキューに格納

print(dist[gx][gy])