[프로그래머스/Python] 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

• +, -를 배열에 담아서 반복문에 돌릴 수 있나?
  (당연 안됨..이런 생각을 하다니 대단해)

👩🏻‍🏫 BFS 풀이

def solution(numbers, target):
    # 트리의 첫 번째 층에는 0
    tree = [0]
    # 매개변수로 받은 숫자 목록을 하나씩 꺼내와 주는 역할
    for num in numbers:
        sub_tree = []
        # 노드 하나하나에 숫자를 더하고 빼주어 자식 노드들을 생성하는 역할
        for tree_num in tree:
            sub_tree.append(tree_num + num)
            sub_tree.append(tree_num - num)
        tree = sub_tree
    return tree.count(target)

• 트리를 한층 한층 밑으로 만들어 나가는 것 = 한 노드에 숫자를 빼고 더한 결과를 자식 노드로 쌓는다.
  

• tree는 이전 수에 대한 계산 결과를 담은 층을 가지고 있고, sub_tree는 현재 숫자에 대한 결과를 담은 자식 노드를 하나씩 추가하는 역할을 한다.

👩🏻‍🏫 DFS 풀이

answer = 0
def dfs(numbers, target, idx, total):
    global answer
    
    if idx == len(numbers):
        if target == total:
            answer += 1
        return
    
    dfs(numbers, target, idx + 1, total + numbers[idx])
    dfs(numbers, target, idx + 1, total - numbers[idx])

def solution(numbers, target):
    global answer
    
    dfs(numbers, target, 0, 0)
    
    return answer

출처
https://jiss02.tistory.com/18
https://johnyejin.tistory.com/60