DFS?

深度優先検索は、最も深い場所にナビゲートして戻り、まだナビゲートされていないノードがある場合は、最も深いナビゲーションプロセスを繰り返すアルゴリズムです.

要点

スタック

を利用

現在のポイント(頂点)が

を移動できるかどうかを確認します.

2

を訪問したのを覚えています.

は次の点があるので、まだ歩けるならナビしてくれますし、なければ戻ってきます.

現在の点に隣接する頂点があるかどうかをチェック

にアクセスしていない場合は、入って戻ってください.

スタックがEmptyになるまで、この手順を繰り返します.

すべてのパスにアクセスする必要がある場合は、

を使用します.

さぎょうモード

ナビゲーションノードをスタック

に挿入する.

スタックの最上位ノードに未アクセスの隣接ノードがある場合、アクセス処理

のためにスタックに入れる.
上記の手順が実行できなくなるまで(再帰的に)

を繰り返します.

サンプル問題(Programmersターゲット番号)

n個の非負の整数.この数字を適当に加算または減算してターゲット番号を作成したいです.たとえば、[1,1,1,1,1,1]で数値3を作成するには、次の5つの方法があります.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.
せいげんじょうけん

で与えられた数字は20個未満です.

各数字

は50より大きい自然数である.

目標は自然数が1000より大きいことです.

番号付けスキーム全体について、個数を求める必要があります.したがって、「重要な情報」で説明したように、DFSはすべてのパスのアクセスポイントとして使用されます.

コード#コード#

var numbersCopy = [Int]()
var targetCopy = 0
var count = 0
 
func DFS(_ depth: Int, _ sum: Int) {
 
    if depth == numbersCopy.count {
        if sum == targetCopy {
            count += 1
        }
        return
    }
    
    DFS(depth + 1, sum + numbersCopy[depth])
    DFS(depth + 1, sum - numbersCopy[depth])
    
}
 
func solution(_ numbers: [Int], _ target: Int) -> Int {
    numbersCopy = numbers
    targetCopy = target
    DFS(0, 0)
    
    return count
}