타겟 넘버

문제

dfs

def solution(numbers, target):
    # 타겟 넘버를 만드는 방법의 수
    answer = 0
    # 깊이 우선 탐색
    def dfs(idx, result):
        # numbers의 길이와 같을 때
        if idx == len(numbers):
            # 결과가 target과 같을 때
            if result == target:
                nonlocal answer
                answer += 1
        # 더하거나 빼기
        else:
            dfs(idx+1, result + numbers[idx])
            dfs(idx+1, result - numbers[idx])
    dfs(0, 0)
    return answer

bfs

from collections import deque

def solution(numbers, target):
    # 타겟 넘버를 만드는 방법의 수
    answer = 0
    # 너비 우선 탐색
    def bfs(idx, result):
        queue = deque()
        queue.append((idx, result))
        while queue:
            idx, result = queue.popleft()
            # numbers의 길이와 같을 때
            if idx == len(numbers):
                # 결과가 target과 같을 때
                if result == target:
                    nonlocal answer
                    answer += 1
            else:
                queue.append((idx+1, result + numbers[idx]))
                queue.append((idx+1, result - numbers[idx]))
            
    bfs(0, 0)
    return answer