DFS系の問題の解き方@JS

JavaScriptでDFSを解くやり方を書いていきます。

重要なポイント

基本的には、下記のような木構造で表せるときにDFSを使うことができる

使うときのポイント
・一番深いときの数値を見つける
・ノード配列を用意する（＜ーノード配列の詳細は後ほど）

一番深いときの数値とは、下記のように木構造があったとき、視点から一番遠いところまでの数のこと
　　

・ノード配列を用意する
ノード配列（ホントは名前とかあるのかもしれないですが、勝手に名付けました。すみません、、）とは
次にノードに行くときに候補として上がる物の配列のこと！
上の写真の場合、
『0』のノード配列は,[1,2,3]
『1』のノード配列は,[4,5] ...
といった具合になる。

このポイントを抑えて、下記テンプレートを使えば、DFSは大体、実装できるはず、、

競プロの問題と参考のコード

これは競プロのC問題。

あなたはスーパーハッカーです。高橋君を攻撃対象に定めたあなたは、
高橋君のパソコンのパスワードに関して次の事実を突き止めました。
長さは
N
文字である。
a, b, c 以外の文字は含まれない。
高橋君のパソコンのパスワードの候補として考えられる文字列をすべて列挙してしまいましょう。

この問題は下のような、◯を視点とした木構造で表せる。
=>DFSが使える！

　　　　　　　　　　|---a---
　　　　　　|-a---b---
　　　　　　|　　　|---c---
　　|-a-b---
　　|　　　|-c---
　　|
◯---b--
　　|-c--

実際のコードがこちら。

index.js

const depth = 3 //一番深い階層（今回は）入力値3が与えられたとする）
const abc = ["a","b","c"] //今回のノード配列

dfs([]) //からの配列を引数に取る

function dfs(arr){
  //（ここの条件は問題によって変わるのでよく考える人用あり）
  if(arr.length === depth) return //配列の長さと深さが一致したらリターンする

  for(let i = 0;i<abc.length;i++){//ノード配列を回す
    arr.push(abc[i])
    if(arr.length === depth){
      ans += arr.join("") + "\n"
    }
    dfs(arr) //再起的に使う
    arr.pop() //末尾削除
  }
}

このコードを実行すれば、下記のような文字列列挙ができる

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc