Let’s 競技プログラミング! E8さんが教えるアルゴリズム発想のキホン(13) 身近な「掃除」を例に考える、「深さ優先探索」とは?

皆さんは「掃除」に対してどんな印象を持っていますか。体力を使う、単純作業で疲れるなど、面倒な作業の代名詞的な印象を持っている人が多いかもしれませんね。しかし、掃除もアルゴリズム発想力を鍛える題材になります。早速見ていきましょう。

掃除の問題

簡単な問題の例として、下図のような家を掃除することを考えましょう。この家は 3 つの部屋（薄いグレーの部分）に分かれていますが、青色で示された部屋Aを掃除するにはどうすれば良いのでしょうか。例えば、下図右側のように、下→右→上→右→右→上→上→下→左という経路で雑巾掛けをすれば、部屋の全てのマスがきちんと掃除されます。

しかし、ロボットに掃除をさせようと思った場合、そう上手くは行きません。ロボットは「一目で部屋全体を認識する能力」を持っておらず、上下左右に隣接するマスが壁であるのか、それとも壁ではないのかという情報しか分かりません。

そこで活躍するのが「深さ優先探索」というアルゴリズムです。隣接する未掃除マスがあれば進み、そうでなければ1歩戻るといったアイデアを使うと、ロボットでも下図のように掃除することができます（既に掃除したマスを赤色で示しています）。

上下左右に隣接するマスが壁であるのか否かでロボットを動かした場合

隣接する未掃除マスがあれば進み、そうでなければ1歩戻る場合のロボットの動作

深さ優先探索とは

それでは本題に入っていきましょう。深さ優先探索はグラフを探索するアルゴリズムの一種であり、英語の「Depth First Search」を略して DFS と呼ばれることもあります。

このアルゴリズムは、掃除ロボットの例と同様に「進めるだけ進み、行き止まりに到達したら1歩戻る」という戦略をベースとしています。例として、グラフが連結かどうか、すなわちどの 2 頂点間も互いに移動可能かどうかを調べたいときのアルゴリズムの流れは以下のようになります。

手順	アルゴリズムの流れ
手順 1	頂点 1 以外の頂点を白色で塗り、頂点 1 を赤色で塗るロボットを頂点 1 から出発させる
手順 2	操作ができなくなるまで、以下の操作を繰り返す隣接する赤色頂点がある：その頂点に進む隣接する赤色頂点がない：1歩戻る
手順 3	操作終了時点で全ての頂点が赤であれば、答えは Yes

深さ優先探索を具体的なグラフに適用させると下図のようになります。なお、下図の太線は経路の跡を示しており、三角形はロボットの現在位置を表します。

深さ優先探索の実装

深さ優先探索を Python で実装する方法はさまざまですが、本連載の第 10 回で取り上げた再帰関数を使うと、非常にシンプルな実装をすることができます。

# 入力データ（頂点数 4、辺が {1, 2}, {2, 3}, {1, 4} の 3 本の場合）
# G[i] は頂点 i に隣接する頂点のリスト（第 12 回参照！）
# color[i]=False のとき頂点 i は白色、True のとき赤色
N = 4
G = [[], [2, 4], [1, 3], [2], [1]]
color = [False, False, False, False, False]

# 再帰関数（ロボットが頂点 pos にいることを意味する）
def dfs(pos):
    for to in G[pos]:
        if color[to] == False:
            dfs(to)
    return

# 実行・出力（このケースでは Yes と出力される）
dfs(1)
Answer = "Yes"
for i in range(1, N+1):
    if color[i] == False:
        Answer = "No"
print("Answer")

このプログラムでは、基本的に以下のような方針でグラフを探索しています。

頂点 to に進む時は dfs(to) を再帰呼び出し
戻る時は return する

つまり「進むときは再帰呼び出し、戻る時は再帰終了」という方針です。なお、頂点数を N、辺数を M とするとき、計算量 O(N+M) で動作します。

第10回「再帰関数とは?」はこちらから

プログラムの具体例

ここまで実装例を紹介しましたが、再帰関数の動きを理解するのは少し難しいかもしれません。そこで下図のようなグラフにおけるプログラムの動作例を見ていきましょう。

ステップ 1

まず、ロボットは頂点 1 から出発するので、関数 dfs(1) が呼び出されます。次に、以下のようなことが起こります。

グラフ上のイベント	再帰関数上のイベント	現時点での再帰構造
頂点 1 から頂点 2 に進む	`dfs(2)` を呼び出し	`dfs(1) -> dfs(2)`
頂点 2 から頂点 3 に進む	`dfs(3)` を呼び出し	`dfs(1) -> dfs(2) -> dfs(3)`

ここまでの流れを図で表すと以下のようになります（グラフと比較してみましょう）。

ステップ 2

次に、頂点 3 に隣接する白色頂点はないので1歩戻ります。そうするとロボットは頂点 2 に移動しますが、ここでも隣接する白色頂点はないので、さらに1歩戻る必要があります。このとき、再帰関数上では次表のようなことが起こります。

グラフ上のイベント	再帰関数上のイベント	現時点での再帰構造
頂点 3 から戻る	`dfs(3)` を終了	`dfs(1) -> dfs(2)`
頂点 2 から戻る	`dfs(2)` を終了	`dfs(1)`

ここまでの流れを図で表すと以下のようになります（グラフと比較してみましょう）。

ステップ 3

次に、ロボットの現在位置（頂点 1 ）と隣接する頂点のうち、白色のものは頂点 4 なので^※、再帰関数中では dfs(4) が呼び出されます。ここまでの流れは下図の通りです。

その後はロボットが新たな頂点を訪問することはないので、次表のようにひたすら戻っていくと、操作が終了します。操作終了時点で全頂点が赤色で塗られている、すなわち color[1], color[2], color[3], color[4] が全て True になっているため、Yes と出力されます。