[Programmers | Level 2] 타겟 넘버 (Python)

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

ans = 0
def solution(numbers, target):
    dfs(0, numbers, target, 0)
    return ans
    
def dfs(s, num, tgt, depth):
    global ans
    if depth == len(num):
        if s == tgt:
            ans += 1
        return
    dfs(s+num[depth], num, tgt, depth+1)
    dfs(s-num[depth], num, tgt, depth+1)

일주일간 플젝 하느라 떨어진 감을 찾기 위해 다시 쉬운것부터 풀어보는 중이다.

DFS로 풀었고, 재귀함수를 이용했다.

from collections import deque

def solution(numbers, target):
    answer = 0
    q = deque([(0, 0)])
    while q:
        sum, i = q.popleft()
        if i == len(numbers):
            if sum == target:
                answer += 1
        else:
            number = numbers[i]
            q.append((sum + number, i + 1))
            q.append((sum - number, i + 1))

    return answer

이렇게 BFS로도 해결할 수 있다.