Day 004-Q1 | BFS基礎

問題

迷路の最短経路を求めよ。H行W列のグリッドが与えられる。S がスタート、G がゴール、. が通れるマス、# が壁。スタートからゴールまでの最短歩数を出力せよ。到達不可能な場合は -1。

入力形式

H W
grid[0]
...
grid[H-1]

制約

$1 \le H, W \le 50$

上下左右に移動可

入出力例

入力例 1

5 5
S....
#####
....#
#####
....G

出力例 1

-1

入力例 2

4 5
S....
.###.
.###.
....G

出力例 2

ヒント (段階的開示)

ヒント1: 方向性

最短経路 → BFS（幅優先探索）。DFSでは最短路は保証されない。

ヒント2: アプローチ

キュー（deque）と dist[r][c] で距離管理。初期: dist=0, queue=[(sr,sc)]。隣接4方向を試して未訪問なら追加。

ヒント3: 誘導

from collections import deque
queue = deque([(sr, sc)])
dist[sr][sc] = 0
while queue:
    r, c = queue.popleft()
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nr, nc = r+dr, c+dc
        if 0<=nr<H and 0<=nc<W and grid[nr][nc]!='#' and dist[nr][nc]==-1:
            dist[nr][nc] = dist[r][c] + 1
            queue.append((nr, nc))

模範解答 (Python)

from collections import deque
import sys
input = sys.stdin.readline

def solve():
    H, W = map(int, input().split())
    grid = [input().strip() for _ in range(H)]

    sr = sc = gr = gc = 0
    for r in range(H):
        for c in range(W):
            if grid[r][c] == 'S':
                sr, sc = r, c
            elif grid[r][c] == 'G':
                gr, gc = r, c

    dist = [[-1] * W for _ in range(H)]
    dist[sr][sc] = 0
    queue = deque([(sr, sc)])

    while queue:
        r, c = queue.popleft()
        if r == gr and c == gc:
            break
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != '#' and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))

    print(dist[gr][gc])

solve()

Step-by-Step 解説

1BFS の基本構造
deque で FIFO。popleft() は O(1)。BFS は近い頂点から順に探索するので、初めて辿り着いた時が最短距離。

2グリッドの隣接表現
DIRS = [(-1,0),(1,0),(0,-1),(0,1)] の4方向。範囲内チェックを必ず行う。

よくあるミス

ミス	原因	正しい書き方
`list.pop(0)`	O(n) で BFS が O(n²)	`deque.popleft()`
訪問済みチェックなし	無限ループ	`dist != -1` で判定
DFSで最短路を求める	DFSは最短路非保証	BFS を使う

Day 004-Q1 — BFS基礎

問題