深さ優先探索をc++で実装してみる
アルゴリズムの超基本らしいです. おはしの持ち方くらい基本らしいです.
再帰苦手なのでスタック使って実装します. アルゴリズムは大体知ってる前提で進めます.
深さ優先探索の例題
競技プログラミングコンテストを開催してるAtCoderの深さ優先探索の例題を解きます. コード書くにあたってグローバル変数をポコポコ使うのは好まないのでクラス作ります. c++感があって自分としてはこっちのが好みです. 汎用性あんまりないけど.
A-深さ優先探索
最初に街の高さと幅が与えられ, つぎに街が二次元配列みたいなんで渡されます. 街を構成する要素(char値)は以下の通り.
'.' : 道. 通れる
'#' : 壁. 通り抜け不可
's' : スタートを表す
'g' : ゴールを表す
's'から始まって道'.'を通り'g'まで到達できるかどうかを判定しろというのが趣旨です.壁は通ることはできないのと範囲外を超えて探索することはできません. アルゴリズムは以下の通り. (ネタバレ注意)
アルゴリズム
開始
↓
街の高さと幅と中身を入力
↓
DFSクラスに街の高さ幅中身入力する
↓
入力された街情報からスタート座標('s')とゴール座標('g')を探す
↓
search()関数で深さ優先探索開始
↓
深さ優先探索でスタートからゴールまでの深さを取得
(ゴールまでたどり着けないなら-1を返すようにする)
↓
到達可能か否か判定してYesかNoを出力する
↓
終了
この方針で作ったので以下にDFSクラスを載せる.
深さ優先探索のクラス
typedef long long llong;
// 深さ優先探索を行うクラス
class DFS {
private:
int sy, sx; // スタート座標
int gy, gx; // ゴール座標
int H, W; // city(街)の高さと幅
int dx[4] = { -1, 0, 0, 1 }; // 注目座標から4近傍を探索するためのxの移動量
int dy[4] = { 0, -1, 1, 0 }; // 注目座標から4近傍を探索するためのyの移動量
struct Coordinate { // xy座標を表す
llong y; // y座標
llong x; // x座標
llong depth; // 深さ(スタート座標では0)
};
vector<string> m_city; // 街
stack<Coordinate> st; // 座標とその深さを保持するスタック
public:
DFS(vector<string> & city) {
m_city = city;
H = city.size(); // 街の高さ
W = city[0].size(); // 街の幅
// スタート座標(sy,sx)とゴール座標(gy, gx)を街から探索してセットする
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
if (city[y][x] == 's') { // スタート地点
sy = y; // スタート地点のy座標
sx = x; // スタート地点のx座標
}
if (city[y][x] == 'g') { // ゴール地点
gy = y; // ゴール地点のy座標
gx = x; // ゴール地点のx座標
}
}
}
};
// 深さ優先探索開始
llong search() {
// まずスタート地点をスタックに格納する
Coordinate start = { sy, sx, 0 }; // y座標, x座標, 深さ(スタートは深さ0)
st.push({ sy, sx, 0 });
// スタックが空になる(完全にcity(街)を探索しきる)まで探索する
while (!st.empty()) {
// スタックの一番上を取ってポップする
Coordinate now = st.top(); st.pop();
// スタックの頂点がゴール座標であるならその時点での深さを返す
if (now.y == gy && now.x == gx) return now.depth;
// 注目してる座標の4近傍(上下左右)を探索
for (int i = 0; i < 4; i++) {
Coordinate next = { now.y + dy[i], now.x + dx[i], now.depth + 1 }; // 深さは+1する
// 街の高さや幅を超える範囲の探索はしない(範囲外エラーになるから)
if (next.y < 0 || H <= next.y) continue;
if (next.x < 0 || W <= next.x) continue;
// 壁だったら無視
if (m_city[next.y][next.x] == '#') continue;
// 既に探索済みなら無視
if (m_city[next.y][next.x] == 'x') continue;
// 探索済みの印(x)を入れておく
m_city[next.y][next.x] = 'x';
// スタックに次の座標と深さをプッシュしておく
st.push(next);
}
}
// 見つからなかったら-1でも返しておく
return -1;
}
};
この問題ではスタート(s)からゴール(g)にたどり着けるかどうかを判定する問題なのでぶっちゃけ深さを返す必要はありません. ですが深さを問われる問題もあるので今回はそれに拡張できるように深さの情報も得られるように作ってあります. 使い方は以下の通りで, DFSクラスのインスタンスを生成してからsearch()関数を呼べばcity(街)のスタートからゴールまでの深さが得られます. もしゴールまで到達できなかったら-1を返すようにしてるのでif文で簡単に判定してやればよいでしょう.
DFSクラスの使い方
int main(void) {
// 高さ, 幅入力
int H, W; cin >> H >> W; // 使ってないけど一応入力
// 街情報の入力
vector<string> city(H);
for (int i = 0; i < H; i++) cin >> city[i];
DFS dfs = DFS(city);
llong depth = dfs.search();
// 深さ優先探索の結果見つからなかったら
if (depth == -1) {
cout << "No" << endl;
}
else { // 見つかったら
cout << "Yes" << endl;
}
return 0;
}
全体としては以下のようになります.
#include <bits/stdc++.h> //iostreamとかstackとかいろいろincludeまとめてる
using namespace std;
typedef long long llong;
// 深さ優先探索を行うクラス
class DFS {
private:
int sy, sx; // スタート座標
int gy, gx; // ゴール座標
int H, W; // city(街)の高さと幅
int dx[4] = { -1, 0, 0, 1 }; // 注目座標から4近傍を探索するためのxの移動量
int dy[4] = { 0, -1, 1, 0 }; // 注目座標から4近傍を探索するためのyの移動量
struct Coordinate { // xy座標を表す
llong y; // y座標
llong x; // x座標
llong depth; // 深さ(スタート座標では0)
};
vector<string> m_city; // 街
stack<Coordinate> st; // 座標とその深さを保持するスタック
public:
DFS(vector<string> & city) {
m_city = city;
H = city.size(); // 街の高さ
W = city[0].size(); // 街の幅
// スタート座標(sy,sx)とゴール座標(gy, gx)を街から探索してセットする
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
if (city[y][x] == 's') { // スタート地点
sy = y; // スタート地点のy座標
sx = x; // スタート地点のx座標
}
if (city[y][x] == 'g') { // ゴール地点
gy = y; // ゴール地点のy座標
gx = x; // ゴール地点のx座標
}
}
}
};
// 深さ優先探索開始
llong search() {
// まずスタート地点をスタックに格納する
Coordinate start = { sy, sx, 0 }; // y座標, x座標, 深さ(スタートは深さ0)
st.push({ sy, sx, 0 });
// スタックが空になる(完全にcity(街)を探索しきる)まで探索する
while (!st.empty()) {
// スタックの一番上を取ってポップする
Coordinate now = st.top(); st.pop();
// スタックの頂点がゴール座標であるならその時点での深さを返す
if (now.y == gy && now.x == gx) return now.depth;
// 注目してる座標の4近傍(上下左右)を探索
for (int i = 0; i < 4; i++) {
Coordinate next = { now.y + dy[i], now.x + dx[i], now.depth + 1 }; // 深さは+1する
// 街の高さや幅を超える範囲の探索はしない(範囲外エラーになるから)
if (next.y < 0 || H <= next.y) continue;
if (next.x < 0 || W <= next.x) continue;
// 壁だったら無視
if (m_city[next.y][next.x] == '#') continue;
// 既に探索済みなら無視
if (m_city[next.y][next.x] == 'x') continue;
// 探索済みの印(x)を入れておく
m_city[next.y][next.x] = 'x';
// スタックに次の座標と深さをプッシュしておく
st.push(next);
}
}
// 見つからなかったら-1でも返しておく
return -1;
}
};
int main(void) {
// 高さ, 幅入力
int H, W; cin >> H >> W; // 使わないけど一応入力
// 街情報の入力
vector<string> city(H);
for (int i = 0; i < H; i++) cin >> city[i];
DFS dfs = DFS(city);
llong depth = dfs.search();
// 深さ優先探索の結果見つからなかったら
if (depth == -1) {
cout << "No" << endl;
}
else { // 見つかったら
cout << "Yes" << endl;
}
return 0;
}
見やすくするために色々冗長になっちゃったけど, 最後のif判定とかは三項演算子使って一行で書いたりする(蛇足).
cout << (dfs.search() == -1 ? "No" : "Yes") << endl;
出力例
問題ページのサンプルにもありますが, 入力と深さ優先探索を実行して得られる出力は以下のようになります.
例1: スタートからゴールまで壁で区切られているので, 到達できないことは誰の目にも明らかでしょう. 当然出力はNoとなります.
// 入力
4 5
s####
....#
#####
#...g
// 出力
No
例2: スタートからゴールまで道'.'を通って到達することが出来ます. ちなみに深さは50となります.
// 入力
10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...
// 出力
Yes
質問やご指摘ありましたらコメントお願いします.