幅優先探索を用いてリモコン操作を最小限に抑える
問題
B: リモコン - AtCoder Regular Contest 001 | AtCoder
解き方
貪欲法でも解けるが、境界線を考慮するのが面倒。そんな時は幅優先を使って全列挙してしまう。
幅優先探索とは
幅優先探索とは、複数の選択肢がある時に、全ての選択肢を順番に試していくというものだ。今回の問題では、リモコンでの操作が6つある。これらの操作を片っ端から順番に行っていく。
幅優先の探索順序は、ルートノードから浅いノードを順番に探索していく。よってリモコンの操作回数とループ回数を対応した時に、初めて条件に当てはまるループ処理の時のループ回数が今回の問題の解になる。
キューを用いた幅優先探索
キューを用いた幅優先探索は以下の流れになる。
- キューを用意
- 評価対象の初めのノードをキューにadd
- キューが空になるまで繰り返し
- キューから先頭のノードを取り出す
- ノードから次の選択肢を選んだ状態の新しいノードを作成
- 上記で作成したノードをキューにadd