幅優先探索で迷路を解いてみた

こんにちは。
今までCheckiOを順調に進めてきたのですが、笑
かなりつまづいた問題があったのでその問題について書きます。

※ ネタバレを含みますのでご注意ください。

まず迷路を解くのにもいろいろな方法があります。
一般的には深さ優先探索や幅優先探索が有名ですが、
それ以外にも様々な方法がありました。
参考URL: http://spheresofa.net/blog/?p=1044

CheckiOの中のヒントでも、幅優先探索が一番手軽だよみたいなことを
言っていたので、今回は幅優先探索でやってみることにしました。

アルゴリズムやプログラムについては、そこまで触れずに
自分のハマったところについて書いていきます。

1.  アルゴリズムは理解できたが、どうやって経路を最終的に出すのかわからない

基本的なアルゴリズムはすぐにわかったのですが、
どうやってスタートとゴールの経路を出すのかがあまりピンときませんでした。
ネットに落ちているプログラムを見てみると、
親要素を持たせて、それをたどっていけばいいだけでした。

2.  QueueモジュールがimportErrorになる

これでかなり時間が取られました。
調べてみるとPython2とPython3でQueueモジュールの名前が変わっていました。
これで解決かと思いきや、CheckiOではQueueモジュールは
サポートされていないとのことでした。
最終的にはcollections.dequeを使いました。

これがgithubにコミットした今回のプログラムです。
https://github.com/junishitsuka/python/blob/master/bfs_maze.py

クラスとか使えばもっとスッキリ書けるんだろうなと思いつつ、
Pythonの勉強がそこまでいっていませんでした。

時間があれば深さ優先探索の方もやりたいですね！