Overview

幅優先探索（BFS: Breadth-First Search）は、グラフ探索の基本中の基本。
1.幅優先探索（BFS）とは
 2.BFSの基本アルゴリズム
 3.BFSの代表的な応用パターン
 4.典型問題を解いてみる

1. 幅優先探索（BFS）とは

BFS（Breadth-First Search）は、グラフ探索の基本アルゴリズムの1つで、「近いノード（距離が小さいノード）から順に調べる」方法。

主に無向グラフ / 有向グラフの最短距離計算に利用される
キュー（Queue）を使って探索順を管理する
キューの記事はこちら
迷路・地図・盤面探索など、現実的な問題に多く登場！

使う場面

無重みグラフにおける最短距離の計算
グリッド上の最短ステップ（例：迷路）
到達可能性の判定（ある点から他の点に行けるか？）

計算量

時間計算量：O(V + E)（V: 頂点数、E: 辺の数）
空間計算量：O(V)（訪問管理＋キュー）

2. BFSの基本アルゴリズム

(1) アルゴリズムの流れ: キューを使って「近い順」に探索

スタートノードをキューに入れる
キューから取り出して、そのノードに隣接する未訪問ノードをキューに追加
これをキューが空になるまで繰り返す

(2) 基本実装

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print("訪問:", node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

3. BFSの代表的な応用パターン

パターン	説明
最短距離計算	頂点 S から各頂点までの距離を配列で持つ（例：dist[v]）
グリッド探索	迷路や盤面での上下左右移動の探索
複数始点の探索	スタート地点が複数ある場合も同時に探索可能（初期キューに複数追加）
経路復元	prev 配列を使って、スタートからゴールまでの道を復元

4. 典型問題を解いてみる

例題1. センサーの島を数えよ

問題:# と . からなる H×W のグリッドが与えられる。上下左右および斜めに隣接する # を「同じ島」とみなし、島の数を数えよ。

参考： ABC325 C - Sensors

回答　

from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
visited = [[False]*W for _ in range(H)]

# 8方向（上下左右＋斜め）
dirs = [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]

def bfs(sx, sy):
    queue = deque([(sx, sy)])
    visited[sx][sy] = True
    while queue:
        x, y = queue.popleft()
        for dx, dy in dirs:
            nx, ny = x+dx, y+dy
            if 0<=nx<H and 0<=ny<W and not visited[nx][ny] and grid[nx][ny] == '#':
                visited[nx][ny] = True
                queue.append((nx, ny))

count = 0
for i in range(H):
    for j in range(W):
        if not visited[i][j] and grid[i][j] == '#':
            bfs(i, j)
            count += 1

print(count)

例題2. 魔法あり最短経路探索

問題:上下左右には通常移動（コスト0）、周囲3×3以内には「魔法」で移動（コスト1）できる迷路。スタートからゴールまでの最短回数を求めよ。

参考： ABC176 D - Wizard in Maze

回答　

from collections import deque

H, W = map(int, input().split())
CH, CW = map(lambda x: int(x)-1, input().split())
DH, DW = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]

INF = 10**9
dist = [[INF]*W for _ in range(H)]
dist[CH][CW] = 0
dq = deque([(CH, CW)])

# 通常移動（コスト0）
normal = [(-1,0),(1,0),(0,-1),(0,1)]

while dq:
    x, y = dq.popleft()
    for dx, dy in normal:
        nx, ny = x+dx, y+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and dist[nx][ny] > dist[x][y]:
            dist[nx][ny] = dist[x][y]
            dq.appendleft((nx, ny))
    # 魔法移動（コスト+1）
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            nx, ny = x+dx, y+dy
            if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and dist[nx][ny] > dist[x][y] + 1:
                dist[nx][ny] = dist[x][y] + 1
                dq.append((nx, ny))

print(dist[DH][DW] if dist[DH][DW] != INF else -1)

例題3. Snukeの順にたどる迷路

問題:グリッドには s, n, u, k, e の文字が並ぶ。スタートから "snuke" の順でたどれるかを BFS で判定せよ。

参考： ABC320 E - Snuke Maze

回答　

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]
order = "snuke"
visited = [[False]*W for _ in range(H)]

dq = deque()
if grid[0][0] == "s":
    dq.append((0, 0, 0))  # (x, y, 今の文字番号)
    visited[0][0] = True

directions = [(-1,0),(1,0),(0,-1),(0,1)]

while dq:
    x, y, t = dq.popleft()
    for dx, dy in directions:
        nx, ny = x+dx, y+dy
        if 0<=nx<H and 0<=ny<W and not visited[nx][ny]:
            if grid[nx][ny] == order[(t+1)%5]:
                visited[nx][ny] = True
                dq.append((nx, ny, (t+1)%5))

print("Yes" if visited[H-1][W-1] else "No")

例題4. 複数の始点からの最短距離

問題:複数のスタート地点があり、それぞれの地点から BFS を同時にスタートし、各ノードまでの最短距離を求める。

参考： ABC321 E - Festival

回答　

from collections import deque

N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)

from_start = list(map(lambda x: int(x)-1, input().split()))
dist = [-1] * N
dq = deque()

for s in from_start:
    dist[s] = 0
    dq.append(s)

while dq:
    v = dq.popleft()
    for nv in graph[v]:
        if dist[nv] == -1:
            dist[nv] = dist[v] + 1
            dq.append(nv)

print(*dist)