[python]BFS/DFSターゲット番号

リンクテキスト
メソッドDFSBSBFS動作原理スタックキューの実装方法再利用可能なキューリソース構造を使用する

DFS(Depth First Search)

DFSはスタートラインから迷路を探索するように突き当たりまで歩き、渋滞に遭遇したら元の場所に戻り、別の方向を探す方法です.

すなわちこの方法はDepth優先探索と呼ばれ,グラフィックにおいて深部を優先的に探索するアルゴリズムであるDepth First Searchである.(番号の低い隣接ノードから開始します.)これは、できるだけ遠くのノードを優先的に参照できることを意味します.

BFS(Breadth First Search)

BFSは、現在の位置ですべての隣接ノードにアクセスし、どこにも行けない場合、アクセスがアクセスノードに接続される方法である.△直感的に見ると、親しい友達を見つけてから、友達を探すことで理解することができます.

すなわちBFSアルゴリズムはBreadth First Searchであり,「幅優先探索」の意味を持つ.すなわち,近接ノードから探索を開始するアルゴリズムである.

問題の説明

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
使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.

せいげんじょうけん

与えられた数字の個数は2個または20個以上である.
各数字は1または50以下の自然数です.
ターゲット番号が1または1000以下の自然数です.

I/O例

numberstargetreturn[1, 1, 1, 1, 1]35[4, 1, 2, 1]42

I/O例説明

問題の例は次のとおりです.
+4+1-2+1 = 4
+4-1+2-1 = 4
そのため、2つの方法があります.
リンクテキスト

もんだいぶんせき

数字を付けると、そうであれば、この2つの状況でツリーを生成できます.

#BFS 풀이
def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    for leaf in leaves:
        if leaf == target:
            answer += 1
    return answer

個の数値を加算または減算して水平位置に追加します.

は、最終的にすべての計算結果をリーフテーブルに含めます.結果出力

再帰関数の使用

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer