dfs(depth-first search)
date: 2021-04-18 excerpt: dfs(depth-first search)について
dfs(depth-first search)について
- 深さ優先探索
- カスタマイズすることでノードがつながった数のカウント等にも使える
- 四畳半で使われる畳(一畳と半畳の畳)で床を敷き詰めるパターンの全探索等
- ネットワーク中の閉路の数を求める
具体的なサンプルコード
i-> 初期ノードarg-> 何らかの挙動のオプションや累積値vis-> すでに訪れたところをスキップするオプション
テンプレート1(再帰あり)
import sys; sys.setrecursionlimit(10**9)
vis = set()
def dfs(i, arg):
if i in vis:
return
vis.add(i)
for j in G[i]:
dfs(j, arg)
テンプレート2(再帰なし, 再帰なしのほうが早い)
def dfs(i, arg):
que = collections.deque([(i, arg)])
while que:
i, arg = que.pop()
if i in vis:
continue
vis.add(i)
for j in G[i]:
que.append( (j, arg) )
例; 具体的な例題とその回答
例; AtCoder Typical Contest 001; A - 深さ優先探索
問題
解説
- 典型的なdfsによるソリューション
解答
例; dfsを適応するとテンプレート的に解ける問題
問題
解答
例; 畳の埋めるパターンをdfsを用いて全探索する
問題
解答
例; queでは解くことができなく再帰でのみ解くことが可能な例
問題
解説
- 状態を記述するデータを次の処理に渡す必要があるが、処理が終わったら戻す必要がある(バックトラック法の一種)
- このデータが大きいとき、queでは参照後リセットを行うというプロセスが記述できないので、必ず再帰として書く必要がある
- 木dpの一種のようにも思える
解答
例; 閉路の検出
問題
解説
- 閉路を含む = 一つのノードに複数個の参照がある, と読み替えることができる
- たどったかどうかを保存するテーブルを工夫し、一つのノードにどれくらい参照があったかをカウントすることで実現できる
解答
例; 探索のパターンの全列挙
解説
- グローバルなvisitedのような変数でたどってきた経路を管理するのではなく、queにたどってきた経路を入れ込むことで、ユニークな経路を列挙することができる
解答
import collections
import itertools
import copy
N,M=map(int,input().split())
G=collections.defaultdict(list)
for _ in range(M):
a,b = map(int,input().split())
a-=1;b-=1
G[a].append(b)
G[b].append(a)
que = collections.deque([[0, []]])
ans = 0
while que:
i, memo = que.pop()
if i in memo:
continue
memo.append(i)
if len(memo) == N:
ans += 1
continue
for j in G[i]:
que.append( (j, copy.copy(memo)) )
print(ans)
例; 距離が偶数か奇数かで塗り分ける
問題
解説
- ２点(a,b)の頂点の距離はある任意の点xからの距離dがある時,
da + db - 2dxになる - この距離の声質を利用して任意の点からのdfsでの距離を記録しておき、偶数か、奇数かで塗り分ける
解答
import sys; sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
u,v,w=map(int,input().split())
u-=1; v-=1
G[u].append( (v,w) )
G[v].append( (u,w) )
vis = set()
mem = dict()
def dfs(i, acc):
if i in vis:
return
vis.add(i)
mem[i] = acc
for j, w in G[i]:
dfs(j, acc+w)
dfs(0, 0)
for i in range(N):
if mem[i]%2 == 0:
print(0)
else:
print(1)
例; 接続したノードの数のカウントアルゴリズム
擬似コード
擬似結果
