bfs力が足りない…!
今、bfs力が非常に足りない。問題を見てbfsだとわからないし、書けない。それを直そう。
とりあえず色々列挙してみる。
- 状態の管理には、queueを使う。イテレーションが少ない時には、配列でヘッドとテイルのポインタやインデクスを持つ形にしてもいい。
- currentとnextの二つのqueue、もしくは配列のテイルを保存しておけば、たとえば深さを状態として明示的に持たずに使える。
- 一度見た状態に戻らないように、setや配列を使う
- 計算量は、木の場合なら時間・空間ともにO(V+E)である
- 配列を使って状態を重複させないようにする場合には、これもO(V+E)でできる
- setを使って重複させないようにする場合は、O((V+E)log V)か?(適当)
- 実際には、少ないイテレーションで答えが見つかる場合、イテレーション毎の分岐をb, イテレーション数をdとすると、O(b^d)となる
- どういう問題に使う?適当に少ないイテレーションで答えが見つかりそうで、dfsだといけなさそうなとき、使えると思う
- とにかく、min(b^d, V+E)な感じで、それが少なくないといけないよね
- とりあえず、そんな感じで、考えには入れよう
- とにかく、今はbfsが考えにも上がらなくて他のことを考えたりしちゃうから、考えに入れよう!
- 状態が進むたびに明らかに大きくなっていくものがあるとき、メモで、pushする時に確認して、小さくできなければpushせず、popするときにも最小より大きいならcontinue、という枝狩りができる