はじめに
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を使う問題はなんとなく苦手意識があるので、
これを気に徐々に慣れていきたいと思います。