microbeの活動日記

プログラミングコンテストなどの活動を書いています

幅優先探索のお話

今回からはアルゴリズムの勉強をちょくちょく挟んでいきます.

 

概要

今回やったのは幅優先探索.

幅優先探索は全探索アルゴリズムの一種で, 深さ優先探索は簡単に理解できたんだけど幅優先探索がなかなかうまく実装できなかったので今回頑張ってやってみた.

解いたのはこの問題.

Mysterious Worm | Aizu Online Judge

赤青緑の3色のうち, 隣り合った2つの色が異なるとき, その2色以外に変化する. すべての色が1色になるまでの最短回数を求める問題. 典型的な幅優先探索の問題らしい. 

 

解法

アルゴリズムは前述のとおり幅優先探索なんだけど大まかにまとめると

1. 初期の状態をキューに入れる.

2. キューから取り出し, 隣り合う異なる色をそれら以外の色に変える.

3. 変えた状態を新たにキューに入れる.

4. 全てが同じ色, またはキューが空になるまで2~3の繰り返し.

ただ,どうやっても1色にならない場合, メモリリミットエラーだったり, いつまでも繰り返しちゃうから, 重複するようならばループを終わらせなきゃいけない.

 

ソースコード

Algorithm

 

結果

f:id:microbe8888:20170110222502p:plain

 

 

いろいろ調べながらではあったけどちゃんと解けたので良し. 深さ優先探索幅優先探索は簡単に実装できるくらいを目標に.

 

こんな感じでアルゴリズムを勉強していきます.