System Design
TTLだけに任せたキャッシュ失効はなぜ危ない？
状況 商品詳細 API のレスポンスを Redis にキャッシュしています。更新時の個別無効化はまだ入っておらず、現在は `TTL=10分` のみで運用しています。 前提 商品価格は運営画面から手動で変更される 商品説明は頻繁ではないが変更...
次の問題へAlgorithms
重みなし最短経路で BFS をまず疑うべきなのはなぜ？
まず考えてから解説へ進みます。答えを覚えるより、判断の理由を言えることを重視します。
Question
まず考える
状況
グリッド上で、始点から終点までの最短移動回数を求める問題です。各移動コストはすべて 1 で、上下左右にだけ進めます。
問い
このとき DFS よりも BFS をまず疑うべきなのはなぜでしょうか。どの特徴が判断材料になりますか。
Notes
- 一番大きい論点を一文で言えるか
- どの条件で問題化するかを分けて考えられるか
- 代替案を出したとき、その引き換えも言えるか
Explanation
解説
最終更新: 2026-04-20
何を見て判断するか
最短経路、重みなし、移動コストが一律という条件がそろった時点で、BFS をまず疑う理由が生まれます。BFS は距離 1、距離 2、距離 3 と層ごとに探索するため、最初に到達した時点の距離が最短になります。
DFS がまずい理由
DFS は深く潜る性質が強く、たまたま見つけた経路が最短とは限りません。全探索に近い形へ寄せないと最短保証を持てず、考えるべきことも実装負荷も増えます。
どこで迷いやすいか
- 「到達できればよい」のか「最短が必要」なのか
- 辺に重みがあるかないか
- 途中で同じ頂点へ再訪する可能性をどう管理するか
実装上の落とし穴
- `visited` を enqueue 時ではなく dequeue 時に付けて重複投入が増える
- 距離管理を別配列にするか、キューにステップ数を持たせるかが曖昧になる
- 始点と終点が同じ場合の扱いを忘れる
補足論点
重み付き最短経路なら Dijkstra や Bellman-Ford など別の選択肢になります。つまり大事なのは「BFS を覚える」ことではなく、「なぜこの条件で BFS が自然か」を判断できることです。
Self Check
この問題の理解度を記録
この記録はこのブラウザに保存されます。あとで見返す問題の整理に使えます。