Pythonで迷路の最短経路を求める｜幅優先探索（BFS）を歩数の地図で理解する

「ゲームの敵って、どうやって壁を回り込んで追いかけてくるの？」

「迷路を解くプログラムを書いてみたいけど、どこから手をつければいいか分からない…」

こんな疑問、ありますよね。実はこれ、どちらも幅優先探索（はばゆうせんたんさく、BFS）という、たった20行ほどのアルゴリズムで解けます。

この記事では、文字で描いた迷路を使って、Pythonの標準機能だけで「スタートから各マスまでの歩数」を数え、最短経路を求めます。最後に、別のやり方（深さ優先探索）と比べて、同じ迷路でも手順によって答えが変わるところまで見ていきます。対象は、リスト・辞書・for文・while文をひととおり読んだ方です。一緒に見ていきましょう！

Contents

迷路を「文字のリスト」で表す
幅優先探索は「近いマスから順に」広げていく
最短経路を「来た道を逆にたどって」求める
深さ優先探索と比べると、答えが変わる
ゲームの「追いかけてくる敵」にも使える
よくあるつまずき ⚠️
まとめ

迷路を「文字のリスト」で表す

maze puzzle / Photo by Monstera Production via Pexels

まずは迷路をPythonで扱える形にします。いちばん簡単なのは、1行を1つの文字列にして、リストに並べる方法です。

# 迷路を文字列で用意する（# は壁、. は通路、S はスタート、G はゴール）
maze_text = """
#############
#S....#....G#
#.###.#.###.#
#...#...#...#
###.#####.###
#...........#
#############
"""

# 1行ずつのリストにする（前後の空行は捨てる）
maze = [line for line in maze_text.splitlines() if line]

# S と G の位置を (行, 列) で探す
for r, row in enumerate(maze):
    for c, ch in enumerate(row):
        if ch == "S":
            start = (r, c)
        elif ch == "G":
            goal = (r, c)

print("大きさ:", len(maze), "行 ×", len(maze[0]), "列")
print("スタート:", start, "ゴール:", goal)
print("maze[1][2] は", repr(maze[1][2]), "/ maze[2][2] は", repr(maze[2][2]))

実行結果：

大きさ: 7 行 × 13 列
スタート: (1, 1) ゴール: (1, 11)
maze[1][2] は '.' / maze[2][2] は '#'

ポイントをまとめるとこんな感じです👇

マスの位置は (行, 列) の組で表す。maze[行][列] でそのマスの文字が取れる
行は上から 0, 1, 2…、列は左から 0, 1, 2… と数える（x, y の順ではないので注意）
迷路のまわりを壁（#）で囲んでおくと、「画面の外に出ていないか」のチェックが要らなくなる

幅優先探索は「近いマスから順に」広げていく

幅優先探索の考え方は、とてもシンプルです。

スタートを「0歩」とする
0歩のマスの隣（上下左右）で、まだ数えていない通路を「1歩」とする
1歩のマスの隣で、まだ数えていない通路を「2歩」とする
…と、数えるマスがなくなるまでくり返す

イメージとしては、スタートに水を1滴たらして、波紋が1マスずつ広がっていく感じです。波紋は近いところから順に届くので、あるマスに最初に届いたときの歩数が、そのマスまでの最短の歩数になります。

「近いところから順に」を実現するのがキュー（待ち行列）です。先に入れたものから順に取り出す入れ物で、Pythonでは collections.deque を使います。

from collections import deque

# 上・右・下・左に1マス進むときの (行の増減, 列の増減)
DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(maze, start):
    """start から各マスまでの最短の歩数を、辞書 {(行, 列): 歩数} で返す"""
    steps = {start: 0}          # 歩数の地図（ここに載ったマス＝もう調べたマス）
    queue = deque([start])      # これから調べるマスの行列（先に入れたものから取り出す）
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRECTIONS:
            nr, nc = r + dr, c + dc
            if maze[nr][nc] == "#":       # 壁には進めない
                continue
            if (nr, nc) in steps:         # 調べ済みのマスは飛ばす
                continue
            steps[(nr, nc)] = steps[(r, c)] + 1
            queue.append((nr, nc))
    return steps


def show_steps(maze, steps):
    """歩数の地図を表示する（壁は ###、たどり着けないマスは ..）"""
    for r, row in enumerate(maze):
        line = ""
        for c, ch in enumerate(row):
            if ch == "#":
                line += "###"
            elif (r, c) in steps:
                line += f"{steps[(r, c)]:3d}"
            else:
                line += " .."
        print(line)


steps = bfs(maze, start)
show_steps(maze, steps)
print("ゴールまでの最短の歩数:", steps[goal])

実行すると、各マスに「スタートから何歩か」を書き込んだ歩数の地図が出ます。

ここが重要です👇

steps は歩数の地図であり、同時に「もう調べたマス」の記録でもある。in steps で調べ済みかを判定している
隣のマスの歩数は「今のマスの歩数 + 1」。これだけで全マスの歩数が埋まる
ゴールは右上なのに、地図は左下まで埋まっている。幅優先探索はゴールの場所を知らなくても、全方向に均等に広がる

これ、実行せずに答えられますか？地図のいちばん大きい数は 16 で、場所はゴールの2マス下です。スタートからもっとも遠い通路がどこかも、この地図を見ればひと目で分かりますね。

最短経路を「来た道を逆にたどって」求める

歩数が分かっても、「どの道を通ればいいか」はまだ分かりません。そこで、各マスについてどのマスから来たかを記録しておき、ゴールから逆にたどります。前のコードの続きに書きます。

def bfs_path(maze, start, goal):
    """最短経路を、通るマスのリスト [start, ..., goal] で返す"""
    came_from = {start: None}   # {マス: どのマスから来たか}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == goal:
            break
        for dr, dc in DIRECTIONS:
            nr, nc = r + dr, c + dc
            if maze[nr][nc] != "#" and (nr, nc) not in came_from:
                came_from[(nr, nc)] = (r, c)
                queue.append((nr, nc))

    # ゴールから「来たマス」を逆にたどって、スタートまで戻る
    path = []
    pos = goal
    while pos is not None:
        path.append(pos)
        pos = came_from[pos]
    return path[::-1]


def show_path(maze, path):
    """通るマスを * にして迷路を表示する"""
    grid = [list(row) for row in maze]
    for r, c in path[1:-1]:      # S と G はそのまま残す
        grid[r][c] = "*"
    for row in grid:
        print("".join(row))


path = bfs_path(maze, start, goal)
show_path(maze, path)
print("歩数:", len(path) - 1)

実行結果：

#############
#S****#****G#
#.###*#*###.#
#...#***#...#
###.#####.###
#...........#
#############
歩数: 14

ポイントをまとめるとこんな感じです👇

came_from は「このマスには、どのマスから来たか」の辞書。スタートだけは None
ゴールから came_from を順にたどるとスタートに戻れる。逆向きに並んでいるので、最後に [::-1] でひっくり返す
ゴールを取り出した時点で break しているので、迷路の残りは調べずに終わる

深さ優先探索と比べると、答えが変わる

迷路を解く方法は、ほかにもあります。よく知られているのが深さ優先探索（DFS）で、「行けるところまでまっすぐ進み、行き止まりになったら1つ戻って別の道を試す」やり方です。再帰を使うと短く書けます。これも前のコードの続きです。

def dfs_path(maze, pos, goal, visited):
    """深さ優先探索：行けるところまで進み、行き止まりなら1つ戻る（下・右・上・左の順に試す）"""
    if pos == goal:
        return [pos]
    visited.add(pos)
    r, c = pos
    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nxt = (r + dr, c + dc)
        if maze[nxt[0]][nxt[1]] != "#" and nxt not in visited:
            rest = dfs_path(maze, nxt, goal, visited)
            if rest:
                return [pos] + rest
    return None


dfs = dfs_path(maze, start, goal, set())
show_path(maze, dfs)
print("深さ優先の歩数:", len(dfs) - 1)
print("幅優先の歩数　:", len(path) - 1)

どちらもゴールにはたどり着いています。でも歩数は、深さ優先が 18、幅優先が 14。深さ優先は「先に見つけた道」をそのまま答えにするので、最短とは限らないんです。

迷路の形によっては、この差がもっと大きくなります。コードはどちらも短く、どちらもちゃんと動く。違うのは手順（アルゴリズム）だけです。

最近は、AIに「迷路を解くPythonのコードを書いて」と頼めば、すぐにコードが返ってきます。でも返ってきたのが深さ優先のコードだったら、「最短経路を求めたい」という目的には合っていません。動いた・ゴールに着いた、だけでは気づけない違いを見分けるには、手順の考え方を自分の言葉で説明できることが大切です。

ゲームの「追いかけてくる敵」にも使える

冒頭の疑問に戻りましょう。壁を回り込んで追いかけてくる敵は、歩数の地図があれば作れます。

プレイヤーの位置をスタートにして、bfs() で歩数の地図を作る
敵は、今いるマスの上下左右のうち、地図の数字が1小さいマスへ1歩進む
プレイヤーが動いたら、地図を作り直す

数字が小さくなる方へ進み続ければ、プレイヤーまでの最短の道をたどれます。敵が何体いても、地図は1枚作るだけでOKです。ゲームの敵が「賢く」見える仕組みも、中身はこの記事で書いた幅優先探索なんですね。

よくあるつまずき ⚠️

キューに入れるときに「調べ済み」にしていない：取り出すときに印をつけると、同じマスが何度もキューに入り、そのぶん無駄に遅くなります。この記事のコードのように、append する前に steps（や came_from）へ登録しましょう
リストの pop(0) でキューを作る：動きはしますが、リストの先頭を取り出すたびに残りを全部ずらすので、大きな迷路では遅くなります。deque の popleft() を使いましょう
(行, 列) と (x, y) を取り違える：maze[行][列] は「縦が先」です。x が横、y が縦の座標と混ぜると、壁をすり抜けたように見えるバグになります