よもやま話β版

よもやま話を書きます。内容はぺらぺら。自由に書く。

BFSの勉強メモ

これの続き: DFSの勉強メモ - よもやま話β版

BFSとは

幅優先探索( Breadth-First Search )のこと。

BFSの例

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の数が増えた。

もっとカンタンなやつをたくさん解かないとどうしようもなさそうなのでこれくらいで…。