《アルゴリズムを学ぶ》24.幅優先探索（BFS）

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

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

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

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

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

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

### (1) アルゴリズムの流れ: キューを使って「近い順」に探索
1. スタートノードをキューに入れる
2. キューから取り出して、そのノードに隣接する未訪問ノードをキューに追加
3. これを キューが空になるまで繰り返す


### (2) 基本実装
```python
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](https://atcoder.jp/contests/abc325/tasks/abc325_c)
<details><summary> 回答　</summary>

```python
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)
```
</details>

### 例題2. 魔法あり最短経路探索
**問題:上下左右には通常移動（コスト0）、周囲3×3以内には「魔法」で移動（コスト1）できる迷路。スタートからゴールまでの最短回数を求めよ。**
>[参考： ABC176 D - Wizard in Maze](https://atcoder.jp/contests/abc176/tasks/abc176_d)
<details><summary> 回答　</summary>

```python
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)
```
</details>

### 例題3. Snukeの順にたどる迷路
**問題:グリッドには s, n, u, k, e の文字が並ぶ。スタートから "snuke" の順でたどれるかを BFS で判定せよ。**
>[参考： ABC320 E - Snuke Maze](https://atcoder.jp/contests/abc320/tasks/abc320_e)
<details><summary> 回答　</summary>

```python
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")
```
</details>

### 例題4. 複数の始点からの最短距離
**問題:複数のスタート地点があり、それぞれの地点から BFS を同時にスタートし、各ノードまでの最短距離を求める。**
>[参考： ABC321 E - Festival](https://atcoder.jp/contests/abc321/tasks/abc321_e)
<details><summary> 回答　</summary>

```python
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)
```
</details>