[프로그래머스/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

21.06.13 수정

문제 해결 과정

• numbers의 값들을 순서대로 + ,- 해준 값을 array에 넣어준다.
• 안쪽 for문의 범위를 보면 idx는 그 전에 추가된 값들의 위치
• 결과값은 array 배열에서 numbers의 마지막 결과 값들 중에서 target인 것들을 count
  • 배열에 값들이 0,2개,4개,8개,16개,32개,,,,으로 추가되니까
  • 마지막 결과값의 위치는 뒤에서부터 찾아서 -를 붙임

시행착오

• 이중포문의 범위 설정
• bfs로 풀려다가.., 포기

풀이

def solution(numbers, target):
    array = [0]
    idx = 0
    for i in numbers:
        for j in range(idx, len(array)):
            array.append(array[j]+i)
            array.append(array[j]-i)
        idx = idx * 2 + 1
        
    return array[-(2**len(numbers)):].count(target)

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