再帰による全探索(深さ優先探索)

例題1 : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

例題通り、[1, 5, 7, 10, 21] のいくつかを足し合わせて [2, 4, 17, 8] を作成できるかを考える
回答例は以下

exhaustive_search.cpp

#include "exhaustive_search.h"
#include <iostream>
using namespace std;

// 入力値は以下とする
static const int N = 5;
static int A[N] = {1, 5, 7, 10, 21};

// i == 加算する数のインデックス
// m == 目標とする和から要素を引いていく。0になればその数を作れる
int exhaustive_search(int i, int m)
{
	if (m == 0) return 1;
	if (i >= N) return 0;
	int res = exhaustive_search(i + 1, m);
	if (res)
		return res;
	else
		res = exhaustive_search(i + 1, m - A[i]);
	return res;
}

main.cpp

#include "exhaustive_search.h"
#include <iostream>
using namespace std;

int main()
{
    const int q = 4;
    int m[q] = { 2, 4, 17, 8 };

    for (int i = 0; i < q; i++)
    {
        if (exhaustive_search(0, m[i]))
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
}

　
再帰を用いてすべての場合を判定する場合、i番目の要素を選ぶか選ばないかのすべての組み合わせを調べることになる。
例えば17を作れるか調べる場合、以下のように遷移する。

例えば8番目では10を使う場合を、11番目では10を使わず7を使う場合を、
14番目では7と21を使う場合をを調べる。
15番目では7と10を使う場合を調べ、17が作成可能であると分かる。
　
　
　
例題2 : 部分和問題(プログラミングコンテストチャレンジブック 34ページ)
解き方は例題1と同じなので、復習として確認する。
今回は目標値から要素を引いていく方法ではなく、すべての和を調べる方法で解く。
dfs.cpp

#include "dfs.h"

const int n = 4;
static const int a[n] = { 1, 2, 4, 7 };
const int k = 13;

bool dfs(int i, int sum)
{
	if (i >= n) return sum == k;
	
	// a[i] を使わない
	if (dfs(i + 1, sum)) return true;

	// a[i] を使う
	if (dfs(i + 1, sum + a[i])) return true;

	return false;
}

main.cpp

#include "dfs.h"
#include <iostream>
using namespace std;

int main()
{
	cout << (dfs(0, 0) ? "Yes" : "No") << endl;
}

　
　
　
例題3 : 2386 -- Lake Counting
大きさがN*Mの森に水溜りができた。水溜りは8近傍で隣接している場合につながっているとみなす。
いくつの水溜りがあるか？
lake_counting.cpp

#include "lake_counting.h"

static const int N = 10, M = 12;
static char field[N][M] = {
	{'W',	'.',	'.',	'.',	'.',	'.',	'.',	'.',	'.',	'W',	'W',	'.',},
	{'.',	'W',	'W',	'W',	'.',	'.',	'.',	'.',	'.',	'W',	'W',	'W',},
	{'.',	'.',	'.',	'.',	'W',	'W',	'.',	'.',	'.',	'W',	'W',	'.',},
	{'.',	'.',	'.',	'.',	'.',	'.',	'.',	'.',	'.',	'W',	'W',	'.',},
	{'.',	'.',	'.',	'.',	'.',	'.',	'.',	'.',	'.',	'W',	'.',	'.',},
	{'.',	'.',	'W',	'.',	'.',	'.',	'.',	'.',	'.',	'W',	'.',	'.',},
	{'.',	'W',	'.',	'W',	'.',	'.',	'.',	'.',	'.',	'W',	'W',	'.',},
	{'W',	'.',	'W',	'.',	'W',	'.',	'.',	'.',	'.',	'.',	'W',	'.',},
	{'.',	'W',	'.',	'W',	'.',	'.',	'.',	'.',	'.',	'.',	'W',	'.',},
	{'.',	'.',	'W',	'.',	'.',	'.',	'.',	'.',	'.',	'.',	'W',	'.',},
};

void dfs(int x, int y)
{
	// 今の点を'.'に置き換える
	field[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;

			// nx, nyが範囲内でfield[nx][ny]が水溜りなら再帰
			if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W')
				dfs(nx, ny);
		}
	}
}

int lake_counting()
{
	int total = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (field[i][j] == 'W')
			{
				dfs(i, j);
				total++;
			}

		}
	}
	return total;
}

main.cpp

#include "lake_counting.h"
#include <iostream>
using namespace std;

int main()
{
    cout << lake_counting() << endl;
}

　
　
　
例題4 : 部分集合の列挙
部分集合の列挙も全探索によって実現できる。
それぞれの要素が選択されている場合とされていない場合を、すべて捜査する。
subset.py

def subset(k, N, a):
    if k < N:
        # 全ての選択肢を再帰で取得する
        a[k] = 0
        subset(k + 1, N, a)
        a[k] = 1
        subset(k + 1, N, a) 
    else:
        # どの要素が選択されているか？
        for i in range(4):
            print(a[i], end=' ')
        print()

        # 表示処理
        print('{', end='')
        initial = 1
        for i in range(N):
            if a[i]:
                if initial != 0:
                    initial = 0
                else:
                    print(', ', end='')
                print(i, end='')
        print("}")


if __name__ == "__main__":
    subset(0, 4, [0]*4)

　
　
　
参考書籍 :
プログラミングコンテストチャレンジブック(https://book.mynavi.jp/ec/products/detail/id=22672)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造(https://book.mynavi.jp/ec/products/detail/id=35408)
再帰の技法??基本的考え方・アルゴリズム・プログラミング | 玉井 浩 |本 | 通販 | Amazon