DFSに入門する

始めに

　今日はDFS(深さ優先探索)に入門しようと思います。先日atcoderのABC204 に挑戦してみたのですが、C問題を見た瞬間「これDFSや～」と分かって諦めてしまったので、ABC204 C問題の解説を見ながらDFSを勉強します。

DFSとは

　wiki引用。　頂点から底まで探索するのを全件試してみるって理解でしょうか。

深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。

ABC204 C問題

ABC204 C問題

有向グラフと捉え、全ノード分DFSを回せばいいようです。解説のPythonのコードをRubyで書き直したのがこちら。

n,m = gets.split.map(&:to_i)

# towns[i]からいける都市のリスト
# Rubyのグローバル変数は$を接頭辞にする
$towns = Array.new(n){[]}
m.times do
  a,b = gets.split.map(&:to_i)
  $towns[a-1] << b-1
end

# DFS
def dfs(v)
  # 一度訪れた都市は探索を終了させる
  return if $temp[v]
  $temp[v] = true
  # DFSの醍醐味
  # 再起関数を使って底まで見ていく
  # グラフなので無限ループに入る恐れがあるが、上記のreturnで途切れるので問題なし
  $towns[v].each{|vv| dfs(vv)} 
end

ans = 0
n.times do |i|
  # iから各都市に行けるかどうか真偽値の配列でカウントする
  $temp = Array.new(n,false)
  dfs(i)
  ans += $temp.select{|el| el}.count
end

puts ans

結び

再帰関数への苦手意識がどうも抜けません。類似問題で要練習ですね。