C++でアルゴリズム入門Part.3

おいしょっと。

ちょっとスピードを上げたいことには変わりないので同日更新ｗ

今回は探索手法をいくつかと、それを使って問題を解いていきます。

深さ優先探索

深さ優先探索(DFS)はある状態からはじめ、遷移できなくなるまで状態を進めていき、遷移できなくなるとひとつ前の状態に戻ることを繰り返す探索手法です。
その性質上、再帰関数でかけることが多いです。

たとえば部分和問題という問題。
与えられた整数のいくつかを選んでその和をある値にできるかという問題。

これは深さ優先探索で、ある数足す足さないの２パターンで分岐していくことでできます。

実際のコードはこんな感じ。

#include <iostream>

using namespace std;

const int MAX_N = 20;
int a[MAX_N];
int n, k;

// iまででsumを作り、残りi以降を調べる。
bool dfs(int i, int sum) {
  // n個決め終わったら今までの和sumがkと等しいかを返す。
  if (i == n) return sum == k;
  // a[i]を足すとき。足したあとtrueが返ってきたらtrueを返す。
  if (dfs(i+1, sum+a[i])) return true;
  // a[i]を足さないとき。上と同様。
  if (dfs(i+1, sum)) return true;
  // どっちもtrueでなかったらfalseを返す。
  return false;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  cin >> k;
  if (dfs(0, 0)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

このように深さ優先探索ははじめの状態から遷移を繰り返すことでたどり着けるすべての状態を生成するので、すべての状態に対して操作を施したり、全状態を列挙できます。
実際にPOJにある問題を見てみましょう。

POJ No.2386
大きさがN×Mの庭があります。そこに水たまりができました。水たまりは８近傍で隣接しているならば同じものとします。全部でいくつあるでしょうか？
(８近傍とは次のWに対する-の部分)
---
-w-
---
制約：N, M ≦ 100

入力などは間違っていますが、方針となるようなコードを載せておきます。

#include <iostream>

using namespace std;

const int MAX_N = 100, MAX_M = 100;
int N, M;
char field[MAX_N][MAX_M + 1];  // 庭

// 現在位置(x,y)
void dfs(int x, int y) {
  // 今いるところを.に置き換える
  field[x][y] = '.';

  // 移動する８方向をループ
  for (int dx = -1; dx <= 1; dx++) {
    for (int dy = -1; dy <= 1; dy++) {
      // x方向にdx y方向にdy 移動した場所を(nx, ny)とする
      int nx = x + dx, ny = y + dy;
      // nxとnyが庭の範囲内かどうかとfield[nx][ny]が水たまりかどうか
      if (0 <= nx && nx < N && 0 <= ny && ny <= M && field[nx][ny] == 'W')
        dfs(nx, ny);
    }
  }
  return ;
}

int main() {
  int res = 0;
  cin >> N >> M;
  for (int i = 0; i < N; i++)
    cin >> field[N];
  for (int i = 0; i < N; i++) {
    for (int j = 0; i < M; i++) {
      if (field[i][j] == 'W') {
        // Wが残っているならそこからdfsを始める→そのWが含まれている水たまりがすべて.に
        dfs(i,j);
        res++;
      }
    }
  }
  cout << res << endl;
}