はじめに

AtCoderでは、よく木を使って解く問題が出題されます。
そこで、今回は深さ優先探索を用いて処理を行うときのコードをまとめました。

例えば以下のような問題です。

この記事が、
DFS（深さ優先探索）について理解する良い機会になると幸いです。

そもそもDFSってなんだっけ

DFS（深さ優先探索）とは、木を探索する手法の一つです。

もう一つの方法に、BFS（幅優先探索）があります。

上の図は、深さ優先探索と幅優先探索で探索するときの順番です。

詳しい説明は省きますが、興味があれば調べてみてください。

２つの違いをざっくりと説明すると、

とりあえず突き進みながら探索するのがDFS（深さ優先探索）
同じ深さのノードを順に探索するのがBFS（幅優先探索）

という感じです。
今回は二分木で表現していますが、二分木でなくても同じです。

実際のコード

では、ここではDFS（深さ優先探索）をPythonで実装してみます。

以下のコードは、「探索済みかどうか」というリストを作って実装していますが、
実際の問題では「各ノードのstart_nodeからの距離を格納するリスト」など、
その場面に合わせたリストに変えて実装してみてください。

dfs.py

def dfs(start_node :int, number_nodes :int, G :list):
    '''
    スタックを使って深さ優先探索
    G は二次元配列で、G[node]の中には nodeとつながっているnode が格納されている
    '''

    did = [0] * number_nodes # 探索済みかどうかを判定するリストを作成
    did[start_node] = 1 # start_node を探索済みにする
    stack = [start_node] # stack には探索したいノードを格納
    
    while (stack): # stack の中身がなくなったら探索終了
        parent_node = stack.pop() # stack からノードを一つ取り出してparent_nodeに格納
        for children_node in G[parent_node]: # parent_nodeと繋がっているchildren_nodeを探索
            if not did[children_node]: # children_node が未探索なら処理を行う
                stack.append(children_node)
                did[children_node] = 1
    
    return did

「そもそもDFSってなんだっけ」で例としてあげた深さ優先探索は、
左から順に探索するように表現してありますが、

このコードを実行すると
（木のノード番号の付け方によって変わりますが、細かいことは置いといて...）
右から順に探索するようになっているはずです。

実際に簡単な木を書いて試してみてください。

最後に

今回はDFSをPythonで実装してみました。

私自身、DFSを使う問題はなんとなく苦手意識があるので、
これを気に徐々に慣れていきたいと思います。