【Atcoder】 DFSとBFS

お久しぶりです、最近は仕事中もAtcoderのあの問題どうやるんだろう・・・と気になってしょうがない日々を過ごしています
今日の話題はDFS(深さ優先探索)とBFS(幅優先探索)の違いと特徴について〜
双方ともある状態からたどり着ける全ての状態を探索する際に使うアルゴリズムですが、それぞれのメリットについてわかっていなかったので蟻本よりメモ

• DFS
  • 再帰関数を使うことで短く書ける
• BFS
  • 最短経路を求めたい時に使える（同じ経路を何度も通るような場合、ただし状態数に比例したメモリが必要）

#DFS
DFSの例は以下のようなフィールドが与えられた場合、何個の水たまり('#')の塊があるか探索する問題。
####入力

4 6 //フィールドのサイズ
#..#..
...#..
#..#..
#..#..

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int H, W;
vector<string> s(H + 100);

void dfs(int x, int y){
 //今いるところを'.'にする
 s[x][y] = '.';
 //8方向を探索
 for(int dx = -1; dx <= 1; ++dx){
   for(int dy = -1; dy <= 1; ++dy){
     int nx = x + dx;
     int ny = y + dy;
     if(0 <= nx && nx < H && 0 <= ny && ny < W && s[nx][ny] == '#'){
       dfs(nx, ny);
     }
   }
 }
 return;
}

int main() {
  //入力
  cin >> H >> W;
  for(int i = 0; i< H; ++i) cin >> s[i];
  int ans = 0;
  
  for(int i = 0; i < H; ++i){
    for(int j = 0; j < W; ++j){
      //水たまりがあるところからスタート
      if(s[i][j] == '#'){
        dfs(i, j);
        ++ans;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

#BFS
BFSの例は以下のようなフィールドが与えられた場合、スタートからゴールまでの最小値を求める問題。
####入力

4 6　//フィールドのサイズ
0 2　//スタート位置
3 5　//ゴール位置
#..#..
......
#..#..
#..#..

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int H, W;
int sx, sy; //スタートの座標
int gx, gy; //ゴールの座標
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; //移動する方向
vector<string> s(H + 100);

typedef pair<int, int> P;

int bfs(){
  queue<P> que;
  int cnt[H][W]; //スタートからの距離を格納する配列
  //初期化
  for(int i = 0; i < H; ++i){
    for(int j = 0; j < W; ++j){
      cnt[i][j] = -1;
    }
  }
  //スタートをキューに入れ、その地点を0にする
  que.push(P(sx,sy));
  cnt[sx][sy] = 0;
  //キューが0になるまでループ
  while(que.size()){
    //先頭のキューを取ってくる
    P p = que.front();
    que.pop();
    //キューがゴールなら探索終了
    if(p.first == gx && p.second == gy)break;
    //移動方向にループ
    for(int i = 0; i < 4; ++i){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(0 <= nx && nx < H && 0 <= ny && ny < W && s[nx][ny] != '#' && cnt[nx][ny] == -1){
        que.push(P(nx, ny));
        cnt[nx][ny] = cnt[p.first][p.second] + 1;
    }
  }
 }
 return cnt[gx][gy];
}

int main() {
  //入力
  cin >> H >> W;
  //スタート位置
  cin >> sx >> sy;
  //ゴール位置
  cin >> gx >> gy;
  for(int i = 0; i< H; ++i) cin >> s[i];

  cout << bfs() << endl;
  return 0;
}

ようやく2つを理解・・・。
蟻本見てるだけだと覚えられなくて、やっぱり自分で書くのが大事そうですね〜