これの続き: DFSの勉強メモ - よもやま話β版
BFSとは
幅優先探索( Breadth-First Search )のこと。
BFSは A → B → C → D → E → F → G → H → I → J → K → L の順で探索する。 BFSは キューを利用し、最短経路を解くケースで使う。
BFSを使って問題を解く
まずはこれをやるといいよ、とオススメしていただいた問題を解いてみる。 https://atcoder.jp/contests/abc007/tasks/abc007_3
ものすごく丁寧に問題内に解き方が載っているので、ありがたく参考にしつつ書いたらACになった。 https://atcoder.jp/contests/abc007/submissions/49629732
今回の学び
- キューの中身全部吐くまで回さないと意味がない
- 先に埋まった手数より短い手数が後から探索されることがあるので、その時は上書きする
おまけ
abc007_3 をやる前と後に、abc317_e にトライしてみていたが、修正したことでACの数が増えた。
- Before: https://atcoder.jp/contests/abc317/submissions/49376354 AC x2 (※サンプルしか解けてない)
- After: https://atcoder.jp/contests/abc317/submissions/49755771 AC x5
もっとカンタンなやつをたくさん解かないとどうしようもなさそうなのでこれくらいで…。
