アルゴリズムのお勉強（１）- 幅優先探索(BFS)

幅優先探索-Wikipedia

やりたいこと

• 幅優先探索について学ぶ

幅優先探索とは

• イラスト付きでものすごくわかりやすく説明されているもの

  • 視覚的にイメージしにくいアルゴリズムを徹底的にイラストで表現するとこうなる (2/4)：CodeZine（コードジン）

• コーディングのイメージもつかめる説明

  • 幅優先探索 - Algoful

幅優先探索実装時に用いるキューの使い方(C++)

• std::queue - C++入門

幅優先探索を用いて解く例題

• AtCoder Grand Contest 033 - AtCoder

  • A問題より抜粋

問題: A - Darker and Darker

入力

制約

1≦H,W≦1000

入力/出力例

入力

3 3
...
.#.
...

出力

2

幅優先探索を用いた実装例(C++)

#include <iostream>
#include <queue>

#define P pair<int,int>
using namespace std;

// マスの縦横
int H,W;
// #,.を格納するマス
char A[1000][1000];

// 幅優先探索の深さを格納するマス
int am[1000][1000];
// 隣り合う辺への移動量
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
// 答え
int ans = 0;
 
void BFS(){
  // 入力を受取り、キューに位置x,yを格納
  cin >> H >> W;
  queue<P> que;
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      cin >> A[i][j];
      if (A[i][j]=='#'){
        am[i][j] = 0;
        que.push(P(i,j));
      }
    }
  }
  // キューを前から取り出し、隣り合う辺が.か#か調べ.なら#に更新し、深さを1足す
  while (!que.empty()){
    P p = que.front();
    que.pop();
    for (int i=0;i<4;i++){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if (nx>=0 && nx<H && ny>=0 && ny<W && A[nx][ny]!='#'){
        A[nx][ny] = '#';
        am[nx][ny] = am[p.first][p.second]+1;
        que.push(P(nx,ny));
      }
    }
  }
}
 
int main(){
  BFS();
  // 答えとなる最も深いものを取り出す
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      ans = max(ans, am[i][j]);
    }
  }
  cout << ans << endl;
  return 0;
}

内容まとめ

• 幅優先探索は上記例のように始点から近い順に網羅的に調べていく手法。

• 実装時にはqueueを使う。

感想

アルゴリズムの勉強楽しい。問題も解き方が多数あるから頭の体操になって良い。

AtcoderのC,D問題が解けるくらいのアルゴリズムを少しずつまとめていきたいな : )