2.スタック・再帰・深さ優先探索(DFS)

2. スタック・再帰・深さ優先探索 (DFS)
佐々木 佑
1
スタック (stack)
スタック (stack) とは, push と pop という 2 つの操作ができるデータ構造です. push はスタックの一番上にデー
タを積む操作です. pop は逆にスタックの一番上からデータを取り出す操作です. つまり, 最後に入れた要素が最
初に出てきます. データを後入れ先出し (FILO: First In Last Out) の構造で保持しています.
図 1: スタックの操作
スタックは配列やリストで簡単に実装できますが, C++の標準ライブラリには初めからスタックというデータ構
造が用意されているのでそれを使うよいでしょう. C++でスタックを使うときは <stack> というヘッダをインク
ルードしましょう.
以下がスタックの使用例です.
#include <iostream>
#include <stack>
using namespace std;
int main(){
stack<int> s;
// int 型をデータとするスタックを用意
s.push( 1 );
// {} => {1}
s.push( 2 );
// {1} => {1,2}
s.push( 3 );
// {1,2} => {1,2,3}
cout << s.top() << endl; // 3
s.pop();
// {1,2,3} => {1,2} 一番上からデータを取り除く
cout << s.top() << endl; // 2
s.pop();
// {1,2} => {1}
cout << s.top() << endl; // 1
s.pop();
// {1} => {}
}
1
問題 Stacking Blocks I(AOJ No.10032)
ロボットを操作して, ブロックの山を作る. 各ブロックにはアルファベット１文字で示された色が着いている.
ロボットは以下の命令を実行する：
• push c : 色がｃであるブロックを山に積む (c は一文字のアルファベット)
• pop : 山の頂点からブロックを１つ取り除く
• quit: 終了する
１つの命令が１行に与えられるので, 取り除かれたブロックの色を順番に出力せよ.
１つの色を１行に出力せよ.
入力
push
push
push
pop
pop
push
pop
quit
a
b
c
t
出力
c
b
t
解答例
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(){
string str;
stack<char> st;
while( cin >> str , str != "quit" ){
if( str == "push" ){
char c;
cin >> c;
st.push( c );
}else if( str == "pop" ){
cout << st.top() << endl;
st.pop();
}
}
}
スタックを使う例題
AOJ No.10032 : Stacking Blocks I
AOJ No.10033 : Stacking Blocks II
AOJ No.0013 : Switching Railroad Cars
2
スタックを使うと括弧の対応を調べることができます. 括弧の種類がひとつだけであれば括弧の初め’(’ が来たら
push して括弧の終わり’)’ が来たら pop するようにします. 括弧の終わりが来たときにスタックが空だったり, 文
字列を調べ終わった後にスタックが空でないときは対応がとれていません.
プログラム例
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(){
string str;
while( cin >> str ){
stack<char> st;
bool flag = true;
for(int i=0 ; i < str.size() ; i++ ){
char c = str[i];
if( c == ’(’ ){ // 括弧の初めが来たら
st.push( c );
}else if( c == ’)’ ){ // 括弧の終わりが来たら
if( st.empty() )
flag = false;
else
st.pop();
}
}
if( flag && st.empty() )
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
入力
(1+1)
3*(1+2)+(2-(4*5))
2*2
(1+1)*(2+(2*3)
)4*(2-3)
出力
Yes
Yes
Yes
No
No
3
問題 The Balance of the World(AOJ No.1173)
複数のデータセットから成り, 各データセットは一行に文字列として与えられる.
データセットの文字列は英文アルファベット， 空白， 丸括弧 (“ ( ) ”) と 角括弧 (“ [ ] ”) の二種類の括弧の
列で， 最後にピリオドがある文字列である.
各データセットについて， 丸括弧 (“ ( ) ”) と 角括弧 (“ [ ] ”) がバランスしていれば“ yes ”を， そうでな
ければ “ no ” をそれぞれ 1 行に出力しなさい．
入力
So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
([ (([( [ ] ) ( ) (( ))] )) ]).
.
.
出力
yes
yes
no
no
yes
yes
4
解答例
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(){
string s;
while( getline(cin,s) ){ // 文字列に半角スペースを含むので 1 行読み込みします
if( s == "." ) break;
stack<char> st;
bool flag = true;
for(int i=0 ; i < s.size() ; i++ ){
char c = s[i];
if( c == ’(’ || c == ’[’ ){ // 括弧の初めが来たら
st.push( c );
}else if( c == ’)’ ){ // 括弧の終わり’)’ が来たら
if( st.empty() || st.top() == ’[’ ){
flag = false;
break;
}else if( st.top() == ’(’ ){
st.pop();
}
}else if( c == ’]’ ){ // 括弧の終わり’]’ が来たら
if( st.empty() || st.top() == ’(’ ){
flag = false;
break;
}else if( st.top() == ’[’ ){
st.pop();
}
}
}
if( flag && st.empty() )
cout << "yes" << endl;
else
cout << "no" << endl;
}
}
括弧の種類が 2 種類に増えているので括弧の終わりが来たときに st.top() で同じ種類の括弧なのか確かめる必要
があります.
この問題は ICPC 2011 の国内予選の問題 B で出題された問題です. このくらいの問題は確実に解けるようにして
おきましょう.
5
例えば 3 + 4 という式を, 演算子 (+) を後に置いて 3 4 + と記述します.
この形式でもっと複雑な式 (1 + 2) ∗ (3 + 4) は 1 2 + 3 4 + ∗ と記述されます.
このような記述方法を逆ポーランド記法 (RPN:Reverse Polish Notation) または, 後置記法 (Postfix Nota-
tion) と言います.
逆ポーランド記法で記述された式はスタックを用いて簡単に計算することができます.
式を最初から順に見ていって数値であればその値をスタックに push して, 演算子であれば 2 回 pop し, 取り出し
た 2 つの値を計算し結果をスタックに push するようにします.
図 2: 逆ポーランド記法とスタックの様子
問題 Strange Mathematical Expression(AOJ No.0087)
複数のデータセットが与えられます. 各データセットでは, 逆ポーランド記法による数式 （数と演算記号が空
白文字１文字で区切られた 80 文字以内の文字列） が１行に与えられます. 各データセットごとに, 計算結果
（実数）を１行に出力してください. なお, 計算結果は 0.00001 以下の誤差を含んでもよい.
入力
10 2 12 - /
3 4 - 7 2 3 * + *
12
2 -3 +
出力
-1.00000000
-13.00000000
12.00000000
-1.00000000
6
解答例
#include <cstdio>
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isNumber(char c){
if( c >= ’0’ && c <= ’9’ ) return true;
return false;
}
int main(){
string s;
while( getline(cin,s) ){
int minusFlag = 1;
double n = 0.0;
stack<double> st;
s += " "; // 入力が数字 1 個のために空白スペースを末尾に追加
for(int i=0 ; i < s.size() ; i++ ){
char c = s[i];
if( c == ’-’ && isNumber(s[i+1]) ){ // 負の数を表す’-’ だったとき
minusFlag = -1;
}else if( isNumber(c) ){ // 数字だったとき
n *= 10.0;
n += c - ’0’;
}else if( c == ’ ’ && isNumber(s[i-1]) ){ // 空白だったとき
n = n * minusFlag;
st.push( n );
n = 0.0;
minusFlag = 1;
}else if( c == ’+’ || c == ’-’ || c == ’*’ || c == ’/’ ){ // 演算子だったとき
double a = st.top();
st.pop();
double b = st.top();
st.pop();
if( c == ’+’ ) st.push( b + a );
if( c == ’-’ ) st.push( b - a );
if( c == ’*’ ) st.push( b * a );
if( c == ’/’ ) st.push( b / a );
}
}
printf("%.8f\n", st.top() );
}
}
int 型だと割り算のときに小数点以下が切り捨てられてしまうので double 型を使うようにします. 問題文に書いて
いませんが負の数 (-2 とか) が含まれていたり, 1 つの行に数字がひとつだけのケースに気をつけましょう.
7
再帰関数
2
関数の中で同じ関数を呼び出すことを再帰呼び出しと言い, 再帰呼び出しをする関数を再帰関数と言います.
階乗 (Factorial) は次のように計算できます.
f act(n) =
1
(n = 0)
n × f act(n − 1)
(n > 0)
プログラムで再帰呼び出しを用いて次のように書くことができます.
int fact(int n){
if(n == 0) return 1;
return n * fact(n-1);
}
再帰関数を書くときには, 必ず関数が停止するように作る必要があります. 先ほどの例では, n = 0 のときには fact
を再帰呼び出しするのではなく直接 1 を返しています. この条件がないと無限に関数を呼び出してしまい, プログ
ラムが暴走してしまいます.
再帰呼び出しの様子
fact(3) => 3 * fact(2)
=> 3 * 2 * fact(1)
=> 3 * 2 * 1 * fact(0)
=> 3 * 2 * 1 * 1
=> 6
問題 Factorial(AOJ No.0019)
整数 n を入力し, n の階乗を出力して終了するプログラムを作成して下さい. ただし, n は 1 以上 20 以下と
します. (※ int 型だと 20! など大きい数字でオーバーフローするので long long int 型を使うこと)
入力
5
出力
120
8
解答例
#include <iostream>
using namespace std;
long long int fact(long long int n){
if(n == 0) return 1;
return n * fact(n-1);
}
int main(){
long long int n;
cin >> n;
cout << fact(n) << endl;
}
次にフィボナッチ数列について考えてみましょう. フィボナッチ数列は次のように定義されます.
f0 = 0, f1 = 1, fn = fn−1 + fn−2
再帰呼び出しを用いてプログラムで書くと次のように書けるでしょう.
int fib(int n){
if(n <= 1) return n;
return fib(n-1) + fib(n-2);
}
この関数を実際に実装すると, fib(40) のような小さな n に対しても計算にかなり時間がかかってしまいます. これ
は, この関数の再帰呼び出しが次のように指数的に広がるためです.
fib(10) => fib(9) + fib(8)
=> (fib(8)+fib(7)) + (fib(7)+fib(6))
=> ( (fib(7)+fib(6)) + (fib(6)+fib(5)) ) + ( (fib(6)+fib(5)) + (fib(5)+fib(4)) )
=> ...
フィボナッチ数列の場合, fib(n) の n の値が一定ならいつ呼び出しても同じ値を返すので, 1 回計算したら配列な
どにメモしておくことで高速化できます. fib(10) を呼び出したときに同じ n で fib が何度も呼び出されるのを見
れば, かなり高速化されることがわかります. これはメモ化探索や動的計画法という考え方で, 後で扱います.
int memo[MAX_N + 1] = {0};
int fib(int n){
if(n <= 1) return n;
if(memo[n] != 0) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
9
深さ優先探索 (DFS)
3
深さ優先探索 (DFS: Depth First Search) とは, 探索手法の 1 つです. ある状態からはじめ, 遷移できなくなる
まで状態を進めていき遷移できなくなったら 1 つ前の状態に戻るというのを繰り替えして解を見つけます. 深さ優
先探索は, その性質上再帰関数で簡単に書けることが多いです.
図 3: 状態の遷移の順番
部分和問題
初めの行に整数 n と k が与えられます. 次の行に整数 a1 , a2 , ... an が与えられます.
整数 a1 , a2 , ... an からいくつか選び, その和を k にすることができるときは ”Yes” を, そうでないときは
”No” を出力しなさい.
制約
1 ≤ n ≤ 20
−108 ≤ ai ≤ 108
−108 ≤ k ≤ 108
入力 (1)
4 13
1 2 4 7
出力 (1)
Yes
入力 (2)
4 15
1 2 4 7
出力 (2)
No
10
a1 から順に加えるかどうかを決めていき, n 個すべてについて決め終わったら, その和が k に等しいかを判定しま
す. 状態数が 2n+1 程度なので計算量は O(2n ) になります. 問題文では添字 i は 1 から始まりますが, プログラム
では 0 から始まるので気をつけましょう.
図 4: 状態の遷移の様子
解答例
#include <iostream>
using namespace std;
int n, k, a[21];
// i までで sum を作って、残り i 以降調べる
bool dfs(int i, int sum){
// n 個決め終わったら, 今までの和 sum が k と等しいかを返す
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;
// a[i] を使う使わないに拘わらず k が作れないので false を返す
return false;
}
int main(){
cin >> n >> k;
for(int i=0 ; i < n ; i++ ){
cin >> a[i];
}
if( dfs(0,0) ){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
11
問題 Split Up!(AOJ 1045)
n 個の整数を入力し, それらを２つのグループ A, B に分けたときの, A に含まれる整数の合計値と B に含ま
れる整数の合計値の差の最小値を出力しなさい.
入力として複数のデータセットが与えられます. 各データセットは以下の形式で与えられます：
n
a1 , a2 , ... an
n が 0 のとき入力の終わりとします.
制約
1 ≤ n ≤ 20
0 ≤ ai ≤ 106
入力
5
1 2 3 4 5
4
2 3 5 7
0
出力
1
1
12
解答例
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1e+9; // 10^9 を表す.
int n, a[21], ans;
// diff は パーティA と B の戦闘力の差
void dfs(int diff, int k){
if( k == n ){ // n 個全部調べ終わったとき
ans = min( ans , abs(diff) );
}else{
dfs(diff + a[k], k+1 );
dfs(diff - a[k], k+1 );
}
}
int main(){
while( cin >> n , n ){
for(int i=0 ; i < n ; i++ ){
cin >> a[i];
}
ans = INF; // 適当に大きな数を代入する
dfs(0,0);
cout << ans << endl;
}
}
a1 から順に A か B のどちらに加えるかどうかを決めその差を計算していきます. n 個すべてについて決め終わっ
たら, パーティA と B の戦闘力の差の最小値を更新します. 状態数が 2n+1 程度なので計算量は O(2n ) になります.
深さ優先探索による全探索で解ける問題
AOJ No.0030 : Sum of Integers
AOJ No.0033 : Ball
AOJ No.1045 : Split Up!
13
問題 How Many Islands?(AOJ 1160)
縦が h, 横が w の地図があります. 地図には陸地と海があり陸地は 8 近傍 (縦横斜め) で隣接しているとき繋
がっているとみなします. 島の数はいくつあるでしょう.
データセットは複数与えられます. 各データセットの形式は以下のとおりです.
wh
c11 c12 ... c1w
c21 c22 ... c2w
...
ch1 ch2 ... chw
cij が 0 のとき海を, 1 のときは陸地を表しています.
入力の終わりは， 空白文字 1 個で区切られた 2 個のゼロのみからなる行で表されます.
制約
1 ≤ w, h ≤ 50
入力
5
1
1
1
1
5
1
0
1
0
1
0
4
1
0
0
0
5
0
0
0
0
0
0
1
1
1
1
0
0
0
1
1
1
1
1
1
0
1
0
1
0
0
0
0
0
1
0
1
0
1
出力
1
9
14
解答例
#include <iostream>
using namespace std;
int w,h;
int field[51][51];
// 現在地 (x,y)
void dfs(int x, int y){
// 今いるところを-1 に置き換える
field[y][x] = -1;
// 移動する 8 方向をループ
for(int dx = -1 ; dx <= 1 ; dx++ ){
for(int dy = -1 ; dy <= 1 ; dy++ ){
// x 方向に dx, y 方向に dy, 移動した場所を (mx,my) とする
int mx = x + dx;
int my = y + dy;
// 範囲外に出たときは次の処理へ
if( mx < 0 || my < 0 || mx >= w || my >= h ) continue;
// 陸地だったら再帰呼び出し
if( field[my][mx] == 1 ){
dfs( mx , my );
}
}
}
}
int main(){
while( cin >> w
for(int y=0
for(int
cin
}
}
>> h , w||h ){
; y < h ; y++ ){
x=0 ; x < w ; x++ ){
>> field[y][x];
int ans = 0;
for(int y=0 ; y < h ; y++ ){
for(int x=0 ; x < w ; x++ ){
if( field[y][x] == 1 ){ // 陸地があったら再帰関数を呼び出す
dfs( x , y );
ans++;
}
}
}
cout << ans << endl;
}
}
深さ優先探索 (DFS) を使うことで繋がっている領域を塗りつぶすことができます. 探索するときは同じ状態を再
び探索しないように探索した状態に −1 を代入するなどを忘れないようにする必要があります. 今回の問題では同
じ状態を再び探索しないように陸地を見つけたら再帰関数 dfs により繋がっている陸地を 1 から −1 に置き換え
ます. main 関数で再帰関数 dfs を呼び出した回数が島の個数となります.
この問題は ICPC2009 年の国内予選の問題 B です. このくらいの問題は確実に解けるように練習しておきましょう.
15
問題 Red and Black(AOJ 1130)
縦が h, 横が w の長方形の部屋があります. タイルの色は赤か黒です.
最初に一人の人が部屋の黒いタイルの上に立っていて, あるタイルからは 4 方向に隣接する黒のタイルにだけ
移動することができます. 赤いタイルには移動できません.
その人が到達できる黒いタイルの数を答えるプログラムを書きなさい.
データセットは複数与えられます. 各データセットの形式は以下のとおりです.
wh
c11 c12 ... c1w
c21 c22 ... c2w
...
ch1 ch2 ... chw
cij はひとつの文字であり, それぞれの文字は次に示すようにタイルの状態を表します.
• ’.’ : 黒いタイル
• ’#’ : 赤いタイル
• ’@’ : 黒いタイルの上の人 (一つのデータセットに 1 度だけ出現)
入力の終わりは， 空白文字 1 個で区切られた 2 個のゼロのみからなる行で表されます.
制約
1 ≤ w, h ≤ 20
入力
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
0 0
出力
45
59
16
解答例
#include <iostream>
#include <string>
using namespace std;
int w, h;
string field[21]; // 文字を扱うので string 型の配列を使うと便利です。
// 4 近傍 (上下左右) のときは次のような配列を用意すると便利
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
// 現在地 (x,y)
void dfs(int x, int y){
// 今いるところを’B’ に置き換える
field[y][x] = ’B’;
// 移動する 4 方向をループ
for(int i=0 ; i < 4 ; i++ ){
// x 方向に dx[i], y 方向に dy[i], 移動した場所を (mx,my) とする
int mx = x + dx[i];
int my = y + dy[i];
// 範囲外に出たときは次の処理へ
if( mx < 0 || my < 0 || mx >= w || my >= h ) continue;
// 黒いタイル’.’ だったら再帰呼び出し
if( field[my][mx] == ’.’ ){
dfs( mx , my );
}
}
}
int main(){
while( cin >> w >> h , w || h ){
for(int y=0 ; y < h ; y++ ){
cin >> field[y];
}
for(int y=0 ; y < h ; y++ ){
for(int x=0 ; x < w ; x++ ){
if( field[y][x] == ’@’ ){ // 人’@’ だったら再帰関数を呼び出す
dfs( x , y );
}
}
}
int ans = 0;
// ループで’B’ の数を数える (到達可能な黒いタイルの数)
for(int y=0 ; y < h ; y++ ){
for(int x=0 ; x < w ; x++ ){
if( field[y][x] == ’B’ )
ans++;
}
}
cout << ans << endl;
}
}
17
今回はフィールドの情報が半角スペースの区切りなしに文字で与えられているので string 型の配列をつかうと便
利です. 開始地点（この問題では’@’）から再帰関数を呼び出します. この再帰関数により到達できるマスを全て
調べることができます.
ICPC で再帰関数を使う場合， いくつかの注意点（テクニック）があります. まず，フィールドの大きさ（W や
H）のような変数はできるだけグローバル変数として宣言しておきます. そうすると main 関数で初期化して再帰
関数を呼び出すときにわざわざ引数を増やす必要がありません. 数千行以上のプログラムを書く場合はグローバル
変数を使いすぎると保守性が下がりますが，保守を考える必要のない 100 行程度のプログラムでは開発効率が上
がって得なのですね.
2 次元配列は f[x][y] ではなく f[y][x] のようにすると入力処理が簡潔になりやすいです.
深さ優先探索で解ける問題
AOJ No.0067 : The Number of Island
AOJ No.0118 : Property Distribution
AOJ No.0207 : Block
AOJ No.0235 : Sergeant Rian
AOJ No.0535 : Crossing Black Ice
AOJ No.1130 : Red and Black
AOJ No.1144 : Curling 2.0
AOJ No.1160 : How Many Islands?
AOJ No.2014 : Surrounding Area
AOJ No.2206 : Compile
AOJ No.2262 : Stopping Problem
参考文献
[1] 秋葉拓哉, 岩田陽一, 北川宜稔: 『プログラミングコンテストチャレンジブック』, 毎日コミュニケーションズ
(2010).
[2] 『 最 強 最 速 ア ル ゴ リ ズ マ ー 養 成 講 座：知 れ ば 天 国 、知 ら ね ば 地 獄 ― ―「 探 索 」虎 の 巻 』,
http://www.itmedia.co.jp/enterprise/articles/1001/16/news001.html
[3] 『ACM/ICPC 国内予選突破の手引き』, http://www.deqnotes.net/acmicpc/
18