(Python/LV2) 타겟넘버

문제 출처:
풀이:

bfs 이용

def solution(numbers, target):

    first = [0]
    for i in numbers:
        lst = []
        for j in first:
            lst.append(j+i)
            lst.append(j-i)
        first = lst
    return first.count(target)

0
0+1 , 0-1
0+1+1, 0+1-1 0-1+1 , 0-1-1

이런식으로 first를 바꿔주면 된다

큐 bfs 이용

from collections import deque
def bfs (numbers, target):
    res = 0
    q = deque()

    length = len(numbers)
    q.append([-numbers[0], 0])
    q.append([+numbers[0], 0])


    while q:
        num, i = q.popleft()
        if i+1 ==length:
            if target == num :
                res += 1
        else:
            q.append([num - numbers[i+1],i+1])
            q.append([num + numbers[i+1],i+1])

    return res

시작에 (-1,0)(1,0) 을 q에 넣어주고
들어온 순서대로 쭊쭉 내려간다.

dfs:

def solution1(numbers, target):
    answer = dfs(numbers,target,0)
    return answer

def dfs(numbers,target, depth):

    answer = 0
    if len(numbers) == depth:
        if sum(numbers) == target:
            return 1
        else: return 0

    else:
        answer += dfs(numbers, target, depth+1)
        numbers[depth] *= -1
        answer += dfs(numbers, target, depth+1)
        return answer

dfs2

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

참고:https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS
dfs는 어려워서 블로그들 보고 이해하고있다