深さ優先探索はなぜ難しいのか

いきなりですがタイトル詐欺です. 正しくは「私にとって深さ優先探索はなぜ難しいのか」です.

この記事を書こうと思ったきっかけですが、DFSの問題を解くときにDFSで解けると分かっていても実装が出来ないということを何度か体験したからです. なので時間をかけてDFSを実装してみたところ、（私にとって）DFSが難しい要因は問題の多様性ではなく、実装の多様性が原因ではないかという結論に至りました. 以下ではDFSを実装するにあたりどのような選択肢があり、私はこれを使って実装するぞ、ということをまとめていきます.

以下ではAtCoder Typical Contest 001-A のように、迷路が与えられてゴールに到着可能かを判定する問題を想定しています.

atcoder.jp

2023/2/14 更新

再帰かスタックか

有名な話ですが、DFSを実装する方法は主に再帰関数を使う方法とスタックを利用する方法があります. 再帰関数の方がかっこいいと思うのですが、スタックで解けるのであればスタックを利用しようと思います. 理由は単純で私にとってはスタックの方が分かりやすいからです. しいて言えばスタックでのDFSに慣れてしまうとC言語で実装しづらくなってしまうことが心残りですが、そこには目をつぶりましょう.

関数かクラスか

DFSを関数の形で実装するかクラスとして実装するかも悩みどころです. おそらく、問題を素早く解かなければならない場合は関数として実装するのが正解なのだと思います. ただ、その場合グローバル変数が多くなってしまうのが少し気になる. ということで時間が許すのであればクラスとして実装しようしたいと思います. そもそもですが、クラスとしてDFSを実装したとしてもその処理の中心はメソッドになるので、どちらを選択しても実装自体はあまり差異がないはず. クラスとして実装するメリットとしては、後からコードを見返したときにわかりやすくなることくらい?

メンバ変数か引数か

クラスとしてDFSを実装するのであればグローバル変数を避けメンバ変数を利用することが出来ます. ただし、DFSに必要なあらゆる情報をメンバ変数にしていては、グローバル変数を用いた場合と同じでどのメソッドでどの情報が必要なのかということが分かりづらいままです. クラスとして実装するメリットを半減させることになってしまいますが、可能な限りメンバ変数を使わずメソッドの引数として情報を渡す方向で行きましょう.

たとえば、DFSに使うスタックをメンバ関数で定義するとメソッドの引数を減らすことが出来ます. ただし、ぱっと見たときにメソッドと変数の関係が分かりません. 特にdfs()の中でスタックをいじっているということが分からないのが致命的に思えます.

#include<stack>

class DFS{
    
    stack<pair<int,int>> st;
    
    void startDfs(){
        st.push(firstNode);
        dfs();
    }

    void dfs(){
        pair<int,int> currPos = st.top();
        for( pair<int,int> nextPos: candidates){
               st.push(nextPos);
               dfs();
        }
        st.pop();
    }
}

一方、変数を引数として渡せばどのメソッドでどの変数が必要かということが明確になります. 少しごついコードになってしまいますが、こちらの方が好みです.

#include<stack>

class DFS{

    void startDfs(const int firstNode){
        stack<pair<int,int>> st;
        st.push(firstNode);
        dfs(st);
    }

    void dfs(stack<pair<int,int>>& st){
        pair<int,int> currPos = st.top();
        for( pair<int,int> nextPos:candidates){
               st.push(nextPos);
               dfs(st);
        }
        st.pop();
    }
}

訪問フラグを立てるタイミング

迷路の問題ではhasVisitedのような2次元配列をフラグとして用意して、訪問済みのマスに対応するフラグをtrueにしておき同じところを重複して訪れることが無いようにします. このフラグを立てるタイミングですが、dfs()の冒頭でタイミングなのか、スタックに積むタイミングなのか、隣接しているマスを数えてる時なのかいつも悩んでしまいます.

たとえば、dfs()の冒頭でフラグを立てるなら次のようなコードになります.

#include<stack>
#include<vector>

class DFS{

    void startDfs(const int firstNode){
        stack<pair<int,int>> st;
        vector<vector<bool>> hasVisited;
        // hasVisited初期化
        ....
        // hasVisited初期化終了
        st.push(firstNode, hasVisited);
        dfs(st, hasVisited);
    }

    void dfs(stack<pair<int,int>>& st, vector<vector<bool>>& hasVisited){

        pair<int,int> currPos = st.top();
        vector<pair<int,int>> candidates;

        // 訪問フラグを立てる
        hasVisited[currPos.first][currPos.second] = true;

        // candidates初期化
        // currPosに隣接してかつ未訪問の座標だけcandidatesにpush_backする
        ...
        // candidates初期化終了

        for( pair<int,int> nextPos: candidates){
            st.push(nextPos);
            dfs(st, hasVisited);
        }
        st.pop();
    }
}

スタックに積むタイミングであれば次のようなコードになります.

#include<stack>
#include<vector>

class DFS{

    void startDfs(const int firstNode){
        stack<pair<int,int>> st;
        vector<vector<bool>> hasVisited;
        // hasVisited初期化
        ....
        // hasVisited初期化終了
        st.push(firstNode, hasVisited);
        dfs(st, hasVisited);
    }

     void dfs(stack<pair<int,int>>& st, vector<vector<bool>>& hasVisited){

        pair<int,int> currPos = st.top();
        vector<pair<int,int>> candidates;

        // candidates初期化
        // currPosに隣接してかつ未訪問の座標だけcandidatesにpush_backする
        ...
        // candidates初期化終了

        for( pair<int,int> nextPos:candidates){
            st.push(nextPos);
            // 訪問フラグを立てる
            hasVisited[nextPos.first][nextPos.second] = true;
            dfs(st, hasVisited);
        }
        st.pop();
    }
}

隣接しているマスを数えているタイミングであれば次のようなコードになります.

#include<stack>
#include<vector>

class DFS{

    void startDfs(const int firstNode){
        stack<pair<int,int>> st;
        vector<vector<bool>> hasVisited;
        // hasVisited初期化
        ....
        // hasVisited初期化終了
        st.push(firstNode, hasVisited);
        dfs(st);
    }

     void dfs(stack<pair<int,int>>& st, vector<vector<bool>>& hasVisited){

        pair<int,int> currPos = st.top();
        vector<pair<int,int>> candidates;

        // candidates初期化
        // currPosに隣接してかつ未訪問の座標だけcandidatesにpush_backする
        ...
        // candidates初期化終了

        // 訪問フラグを立てる
        for(const pair<int,int> candidate:candidates){
            hasVisited[candidate.first][candidate.second] = true;
        }

        for( pair<int,int> nextPos:candidates){
            st.push(nextPos);
            dfs(st, hasVisited);
        }

        st.pop();
    }
}

少なくともAtCoder Typical Contest 001-Aに関してはいずれもできましたが、もしかすると問題によってはACできないこともあるのかもしれません. また、BFSの問題でキューに積むタイミングにフラグを立てないとACできないことも経験したことがあります.

なんとなくですが一番最後、つまり隣接マスを数えているタイミングで訪問フラグを立てる方針で行きたいと思います. 見た目が一番すっきりしてますしね.

breakができないがどうするか

単純なforループであればゴールに到着した瞬間breakすればすぐさま元の処理に戻ることが出来ます. しかし、スタックを用いたDFSの場合そうはいきません. ナイーブに実装するならばgotoを使うか、そもそも早期リターンをあきらめて探索可能な箇所をすべて訪問してからゴールのフラグを確認することになります. 速度にこだわりがないのであれば探索可能な箇所をすべて訪問してもよいと思いますが、せっかくクラスとして実装しているのでゴールに到着済みかのフラグをメンバ変数に持たせる方針で行きましょう. ただ、この方針だとコードが少し複雑になるデメリットがあるので(特にゴールの座標の情報が必要になって面倒)、覚悟しましょう. また、訪問フラグと同様にスタックに積むタイミングでゴールフラグを立てるか、dfs()の冒頭でゴールフラグを立てるかの問題が出てきます. 特に理由がなければ訪問フラグと同じスタックに積むタイミングでゴールフラグを立てる方針で行きましょう. dfs()の冒頭での早期リターン判定も忘れずに.

#include<stack>
#include<vector>

class DFS{

    bool canVisitGoal;

    void startDfs(const int firstNode){
        stack<pair<int,int>> st;
        vector<vector<bool>> hasVisited;
        pair<int,int> goalPos;
        // hasVisited初期化
        ....
        // hasVisited初期化終了
        canVisitGoal=false;
        st.push(firstNode, hasVisited, goalPos);
        dfs(st, hasVisited, goalPos);
    }

     void dfs(stack<pair<int,int>>& st, vector<vector<bool>>& hasVisited, pair<int,int> goalPos){
        
        if(canVisitGoal){
            // ゴールフラグがtrueならポップだけして早期リターン
            st.pop();
            return;
        }

        pair<int,int> currPos = st.top();
        vector<pair<int,int>> candidates;

        // candidates初期化
        // currPosに隣接してかつ未訪問の座標だけcandidatesにpush_backする
        ...
        // candidates初期化終了

        // 訪問フラグを立てる
        for(const pair<int,int> candidate:candidates){
            hasVisited[candidate.first][candidate.second] = true;
        }

        for( pair<int,int> nextPos:candidates){
    
            if(nextPos == goalPos){
                // ゴールフラグを立てる
                canVisitGoal = true;
            }

            st.push(nextPos);
            dfs(st, hasVisited, goalPos);

        }
        st.pop();
    }
}

より効率を求めるならnextPosをスタックにプッシュする前にcanVisitGoalの判定をするとか、ゴールの座標はスタックにプッシュしないとかあると思いますが、実行スピードに大した差は出ないでしょう. ソースコードの読みやすさと実行効率の折衷案としてはこの辺がちょうどよいのではないでしょうか.

最終的に欲しい情報はなんなのか

AtCoder Typical Contest 001-A はゴールに到着できるか否かを判定する問題でした. これがもしゴールに到着するまでの道順をスタート地点から順に表示しろという問題であったら少しばかり改変する必要がありますね. しかもスタート地点から順番となると、LIFOのスタックとは相性が悪い. その場合、そもそもDFSを配列やdequeで実装した方が早い. 配列やdequeをスタックのように使うので、スタックで実装していることには変わりない.

その場合dfs()の目的は配列やdequeを返すことになりますが、戻り値の型はvoid型のままで実装したいのでここでもやはりメンバ変数を使いましょう.

#include<vector>
#include<algorithm>  

class DFS{

    bool canVisitGoal;
    vector<pair<int,int>> ret;

    void startDfs(const int firstNode){
        vector<pair<int,int>> vec;
        vector<vector<bool>> hasVisited;
        pair<int,int> goalPos;
        // hasVisited初期化
        ....
        // hasVisited初期化終了
        canVisitGoal=false;
        vec.push_back(firstNode, hasVisited, goalPos);
        dfs(vec, hasVisited);
    }

     void dfs(vectorpair<int,int>>& vec, vector<vector<bool>>& hasVisited, pair<int,int> goalPos){
        
        if(canVisitGoal){
            // ゴールフラグがtrueならポップだけして早期リターン
            vec.pop_back();
            return;
        }

        pair<int,int> currPos = st.top();
        vector<pair<int,int>> candidates;

        // candidates初期化
        // currPosに隣接してかつ未訪問の座標だけcandidatesにpush_backする
        ...
        // candidates初期化終了

        // 訪問フラグを立てる
        for(const pair<int,int> candidate:candidates){
            hasVisited[candidate.first][candidate.second] = true;
        }

        for( pair<int,int> nextPos:candidates){
    
            if(nextPos == goalPos){
                // ゴールフラグを立てる
                canVisitGoal = true;
                // 道順をコピー
                copy( vec.begin(), vec.end(), ret.begin() );
            }

            vec.push_back(nextPos);
            dfs(st, hasVisited, goalPos);
        }
        vec.pop_back();
    }
}

以上でDFSを解くためのテンプレート完成です.

まとめ

DFSに限らずですが、実装が自由すぎるとかえって難しいということがよくわかりました. また、stackとvectorとdequeでメソッドが微妙に異なるのが煩わしいですね. そのうちコンテナのメソッドをまとめたい.

参考

cpprefjp.github.io