競技プログラミング講習/DFS

概要

今回は、DFSについて解説します。迷路の探索を取り扱っていきますが、実際はグラフの問題で多く使います。 グラフへの応用はグラフの章を読んでください。

重要語

DFS

深さ優先探索。ある地点とある地点が連結であるかを調べることができる。

再帰関数

自分自身を呼び出す関数のこと。

必要語

今回の必要語はありません。

DFS

DFS(depth first search, 深さ優先探索)を用いると、迷路のスタートからゴールまでがつながっているかを調べることなどができます。 スタートからゴールまで到達可能かということは、BFS(次章)を使っても調べることができますが、DFSはグラフの探索において非常に有効です。 DFSは、とにかく進めるところまで進んで進めなくなったら戻る、といったイメージです。

探索する迷路

ここでは、例として図のような迷路の探索を考えてみましょう。 白いマスが通行可能な空きマス、黒いマスが通行不可能な壁マス、sがスタート、gがゴールを表しています。 通行可能なマスからは、上下左右に隣接する通行可能なマスに移動することができます。 迷路の外に移動することや、壁マスへ移動すること、斜めに移動することはできません。 スタートからゴールまで到達可能かを判定してみましょう。

Step1

まず、スタートを探索済みにします。

Step2

右左上下の順で探索することにして、分かれ道を気にせず右にどんどん進め、そこを探索済みにしていきます。

Step3

ここで右に行けなくなってしまったため、次は左を見ますが、ここはすでに探索済みであるためパスし、 次に上を見てここはまだ探索していないためそこを探索済みにします。

Step4

ここで上下左右どこにも行けなくなってしまったためひとつ前の地点に戻り、そこから新たに行けるところがないかを探します。

Step5

もし探索できるところがあればそこを起点に同様に探索していきます。

Finish

後は同じように探索をしていき、スタートに帰ってきたら終了です。

実装例

それでは、実装例を見ていきます。DFSの実装は再帰関数を使った実装や、スタックを使った実装などがありますが、 今回はより簡潔に書ける再帰関数のほうを紹介します。なぜ再帰関数でうまくいくかというと、最初はスタート地点の座標で呼び出され、 その後4方向を見るときに、±1で呼び出されさらにそこから...というようにどんどん進んでいき、4方向が終わったらreturnして終了するためです。
左上(0,0)をスタート地点として、縦Hマス横WマスのH×Wマスからなる迷路を探索し、右下(w-1,h-1)のゴールにたどり着けるかどうかを判定します。
入力の形式は、1行目にH,Wが与えられ、2行目からのH行には迷路の各マスの情報が#は壁で.は道として与えられることを想定しています。
DFS 
#include <bits/stdc++.h>
using namespace std;
void dfs(int x, int y, int h, int w, vector<vector<bool>> &isR, vector<string> &s) {
    // 範囲外アクセスしないように迷路の外だったら即return
    if (0 > x || x >= w || 0 > y || y >= h) return;
    // そのマスが探索済みまたは壁であってもreturn
    if (isR[y][x] || s[y][x] == '#') return;
    // このマスを探索済みにする
    isR[y][x] = true;
    // 4方向を見る
    dfs(x + 1, y, h, w, isR, s);
    dfs(x - 1, y, h, w, isR, s);
    dfs(x, y + 1, h, w, isR, s);
    dfs(x, y - 1, h, w, isR, s);
    return;
}
int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    vector<vector<bool>> isR(h, vector<bool>(w, false));
    dfs(0, 0, h, w, isR, s);
    if (isR[h - 1][w - 1]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

計算量

では、DFSの計算量はどうなるでしょうか。DFSにおいて、1つのマスにつき1回しか見ることはありません。そのため、計算量はO(HW)になります。

練習問題

理解できたか確認するために、練習問題を解いてもらいます。以下の問題を解いてみてください。
(練習問題が少なくてごめんなさい。ほとんどグラフの問題でした...)