深さ優先探索

大学の講義の方で深さ優先探索( depth- first search : DFS ) や 幅優先探索( breath-first search : BFS ) について学んではいたが 実際にコードを書く経験はあまりなかったので訓練目的で以下の問題を解いて見ます

AtCoder Typical Contest の問題 atc001.contest.atcoder.jp

概要

スタック( Stack ) と キュー ( Queue )

深さ優先探索と幅優先探索の違いは, スタック ( Stack ) を用いるのか or キュー ( Queue ) を用いるのかという違いだけです.

スタック, キューはともにデータの保存 および 取り出しの機能を持つデータ構造です.

• スタック( Stack )
  保存したデータから新しいものから取り出すことができます.
  1, 2, 3, ... 10 の順番にデータを詰めたとしたら, 10, 9, 8 , ..., 1の順番で取り出されます.
  

  • 例 ) 思いつかなかったので, ここでは 僕のカバンにしておきます( 笑 )
    
    

• キュー ( Queue )
  逆に古いものから取り出すことができます.
  すなわち, 1, 2, 3, ..., 10 の順番にデータを詰めたとしたら, 1, 2, 3, ..., 10 の順番で取り出されます.
  

  • 例 ) ロケット鉛筆や, レジやラーメン屋の順番待ち

深さ優先探索と幅優先探索

以上のデータ構造の違いによって深さ優先探索と幅優先探索の違いが生まれます.

深さ優先探索は, スタック ( Stack ) を用いて 1方向に対してどんどん掘り下げていきます.

一方で, 幅優先探索は, 始点の位置から「距離が 1 のものを全て調べる」→「距離が 2 のものを全て調べる」

→ ... →「距離が n のものを全て調べる」... という風にグラフを調べていきます.

これらについての詳しい説明は

mathtrain.jp

などのもっと素晴らしいサイトを参照していただければ良いと思います.

My Answer

関数 dfsの引数に於いて, int aとなどとせずに, int &aとアドレスをするように, 引数に受け取るようにして
参照渡しとすることで, 関数 dfs 内部 Stackの反映が, main内のスタックに反映させられるようにしています.

// テンプレは省略
// 型の略称
using vc = vector<char>;
using vcc = vector<vc>;
using vb = vector<bool>;
using vbb = vector<vb>;

int n, m;

/* 深さ優先探索 ; ゴールに到着したら, true, 
                それ以外は スタックに詰めて falseを返す関数 */
bool dfs(int i, int j, vcc &dt, stack<pii> &st, vbb &ccd){
  if(0 <= i && i < n && 0 <= j && j < m){ // 配列内参照かチェック
    if(dt[i][j] == 'g') return true;
    if(dt[i][j] == '.' && !ccd[i][j]){ // 未到着でいける場所
      st.push(make_pair(i, j));
      ccd[i][j] = true;
    }
  }
  return false;
}


int main(){
  // 入力値の受け取り
  cin >> n >> m;
  int sx, sy, gx, gy;
  vcc data(n, vc(m)); char k;
  REP(i, n) REP(j, m){
      cin >> k;
      if(k == 's'){
        sx = i; sy = j;
      }
      else if(k == 'g'){
        gx = i; gy = j;
      }
      data[i][j] = k;
  }

  vbb checked(n,vb(m, false)); checked[sx][sy] = true;
  string yes = "Yes", no = "No"; // 出力用文字列
  stack<pii> search;  // スタック 
  search.push(make_pair(sx, sy));
  // 探索を行う
  while(!search.empty()){
    pii tmp = search.top(); search.pop(); // データの取り出し
    int x = tmp.first, y = tmp.second;
    bool TTT = dfs(x - 1, y, data, search, checked)
            || dfs(x + 1, y, data, search, checked)
            || dfs(x, y - 1, data, search, checked)
            || dfs(x, y + 1, data, search, checked);
    if(TTT){
      cout << yes << "\n";
      return 0;
    }
  }
  cout << no << "\n";
  return 0;
}