深さ優先探索入門
今回の参考資料です。
実践・最強最速のアルゴリズム勉強会 第二回講義資料(ワークスアプリケーションズ & AtCoder)
例題
まずN人にM個のリンゴを配る組み合わせの数を出力するプログラムを考えます。
main()
{
//入力を受け取ります
int n,m; cin>>n>>m;
int ans=0;
cout<<ans<<endl;
}
「N人にM個配る組み合わせ数」は、
「１人目に０個配り、N－１人にM個配る組み合わせ数」と、
「１人目に１個配り、Nー１人にMー１個配る組み合わせ数」と、
・
・
・
「１人目にM個配り、Nー１人に０個配る組み合わせ数」の合計で求められます。
再帰的に書けそうです。
dfs(n,m)=dfs(n-1,m)+dfs(n-1,m-1)+...+dfs(n-1,0)
実装してみます。
int dfs(int n,int m) { int res=0; for(int i=0;i<=m;i++) { res+=dfs(n-1,i); } return res; }
また、ｎ＝１の場合これは「１人にM個配る組み合わせ数」を表します。
１人でリンゴを総取りする以外ないのでこれは１をreturnさせてよいです。
int dfs(int n,int m) { if(n==1)return 1; int res=0; for(int i=0;i<=m;i++) { res+=dfs(n-1,i); } return res; } main() { int n,m; cin>>n>>m; int ans=dfs(n,m); cout<<ans<<endl; }
大きい問題（ｎ人）を小さい問題（１人とそれ以外）に分けて考えています。
この「それ以外」の人数が１人になる深さまで探索して最後にそれらの合計をreturnさせるアルゴリズムなんだなあと解釈しました。
例題その２
深さ優先探索というとやはりマス目の中を探索していくイメージがあります。
第１回ARCのC問題を考えます。
８クイーン問題です。レイトン教授に似た問題がありました。
高々６４マスなので、本番でこの問題に出遭った場合には全探索するかもしれません。
char board[8][8],ans[8][8]; bool flag; main() { //入力受け取り for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cin>>board[i][j]; } } //出力 if(flag) { for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cout<<ans[i][j]; } cout<<endl; } }else { cout<<"No Answer"<<endl; } }
とりあえず入出力だけを書きました。
方針が立たないので、まず「ある空きマス（ｘ、ｙ）に１つのクイーンを置いてもよいか」を調べる関数を作ることにします。
※次の中タイトルまでしばらくDFSの準備のための実装が続きます。
８方向を考える前に、
まず「現在の位置から左上方向にクイーンがないか」だけを調べて、判定を返すコードを書いてみましょう。
bool isOK(int y,int x) //OKるかOKないか（置けるか置けないか） { //左上 int ty=y,tx=x; int dy=-1,dx=-1; while(true) { ty+=dy; tx+=dx; if(board[ty][tx]=='Q')return false; } return true; }
これでは無限ループとなってしまいます。
盤面の外に出た場合には調べる前にbreakさせましょう。
bool inBoard(int ty,int tx) { if( 0<=ty&&ty<=7 && 0<=tx&&tx<=7 )return true; return false; } bool isOK(int y,int x) { //左上 int ty=y,tx=x; int dy=-1,dx=-1; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } }
左上方向に移っていくのでｘとｙを１ずつ小さくしていけばよいです。
この調子で左上だけではなく、真上方向と右上方向も実装してみます。
bool isOK(int y,int x) { //左上 int ty=y,tx=x; int dy=-1,dx=-1; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } //真上 ty=y;tx=x; dy=-1;dx=0; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } //右上 ty=y;tx=x; dy=-1;dx=1; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } return true; }
ここで、「左上」「真上」「右上」は、dx の値を変えただけでやっていることは同じ操作であることが分かるかと思います。
これはその他の方向についても同様で、ｄｘとｄｙのパターンは-1 0 1の３通りずつしかありません。この組み合わせによってどの方向へ移っていくのかが決定されます。
これはfor文を使って以下のようにまとめられます。
bool isOK(int y,int x) { int ty,tx; for(int dy=-1;dy<=1;dy++) { for(int dx=-1;dx<=1;dx++) { if(dy==0&&dx==0)continue; ty=y; tx=x; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } } } return true; }
ｄｙ＝０かつｄｘ＝０の時には、移動がありませんので、continueさせておく必要があります。
ここまでのコードを利用すると、
「整数ｘ、ｙと８×８のマス目を入力とした時に、空きマス（ｘ、ｙ）にクイーンを置けるか」を判定するプログラムが作れます。
using namespace std; char board[8][8]; bool inBoard(int ty,int tx) { if( 0<=ty&&ty<=7 && 0<=tx&&tx<=7 )return true; return false; } bool isOK(int y,int x) { int ty,tx; for(int dy=-1;dy<=1;dy++) { for(int dx=-1;dx<=1;dx++) { if(dy==0&&dx==0)continue; ty=y; tx=x; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } } } return true; } main() { int x,y; cin>>x>>y; for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cin>>board[i][j]; } } if(isOK(y-1,x-1))cout<<"OKru"<<endl; else cout<<"OKnai"<<endl; }
これで準備ができました。
次にどうやって深さ優先探索していくかについて考えます。
どうやる
方針としては、
「とりあえず目の前のマスAにクイーンを置けるのなら、置く。次の空きマスを見ていって、8個全て置けるかを試す。最後まで置けなかったのならば、マスAは置いてはいけなかった場所ということになるので置かないことにする。次のマスを見る。（以下繰り返し）」
ということになるかと思います。
2次元盤面ですが、方針より、1次元的に走査していきますので各64マスに番号を振ります。*1
「０番から６３番まで探索したときにクイーンを８個置けるかどうか」を、dfs(0,8)と表します。
- ０番にクイーンを置くとした場合、残りのマスに７個のクイーンを置けるか知りたいため、
dfs(0,8)→dfs(1,7)と遷移させます。
dfs(1,7)は「１番から６３番までで７個クイーンを置けるか」を表します。 - ０番にクイーンを置かないとした場合、残りのマスに８個のクイーンを置けるか知りたいので、
dfs(1,8)を調べます。
このように考えると第２引数は「残りクイーンの数」と捉えられます。
「残りクイーンの数」が０となれば全て置けたということなので true を返せます。
最後のマスを調べても「残りクイーンの数」が０となっていない場合には、false を返します。
bool dfs(int pos,int nokori) { if(nokori==0)return true; if(pos==64)return false; }
探索していきましょう。
まず入力から、現在のpositionにすでにクイーンが置かれている場合、「置かない」という選択肢は取れないので「置けるかどうか」のみを調べます。
//必ず置かないといけない if(board[y][x]=='Q') { //置けるのか if(isOK(y,x)) { //置けるのならば遷移させてみる。遷移先がtrueならtrueを返せる。 if(dfs(pos+1,nokori-1))return true; }else { //そもそもここに置けないのならゲームオーバーなのでfalseを返す return false; } }
つぎに空きマスについて調べる場合を考えます。
クイーンは置いてもいいし置かなくてもいいです。
ので、遷移先は２つあります。
そのどちらもがfalseである場合には、置いても置かなくても最後までたどり着けないルートということが分かります。falseを返します。
//置けるのか if(isOK(y,x)) { //置けるのならば遷移させてみる。遷移先がtrueならtrueを返せる if(dfs(pos+1,nokori-1))return true; } //置くルートがダメだった場合（なのでelseにしない） if(dfs(pos+1,nokori))return true; //置かないので残りのクイーンの数nokoriはそのまま
ところでこの問題の出力形式はクイーンを８個置いた完成図を出力しないといけないので、探索しながらその図も作らないといけません。
なので、それを考慮しつつbool dfs(int pos,int nokori)を完成させます。
bool dfs(int pos,int nokori) { if(nokori==0)return true; if(pos==64)return false; int y=pos/8; int x=pos%8; if(board[y][x]=='Q') { if(isOK(y,x)) { if(dfs(pos+1,nokori-1))return true; }else { return false; } }else { if(isOK(y,x)) { board[y][x]='Q'; //置いた if(dfs(pos+1,nokori-1))return true; else board[y][x]='.'; //置いてダメだったようなので取った } if(dfs(pos+1,nokori))return true; } return false; }
これにて完成です。（提出コード）
ここまでお読みいただきありがとうございました。
