[DFS/BFS] 타겟넘버

풀이1- DFS

def solution(numbers, target):
    answer = 0
    length = len(numbers)

    def dfs(tmp, count):
        #종료조건
        if count == length-1:
            if tmp == target:
                nonlocal answer
                answer+=1
            return

        dfs(tmp+numbers[count],count+1)
        dfs(tmp-numbers[count],count+1)
    dfs(0,-1)
    return answer

예전에 풀었던 방식
nonlocal을 사용하지 않는 방법으로 dfs함수를 solution함수 밖으로 빼내어 numbers를 매개변수로 전달해주는 것을 생각해보았는데 무엇이 더 좋은 방법인지 모르겠다.

풀이2- BFS

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque()
    queue.append(0)
    
    for num in numbers:
        for i in range(len(queue)):
            sum = queue.popleft()
            queue.append(sum+num)
            queue.append(sum-num)
    
    answer = queue.count(target)
    return answer

BFS를 사용하여 풀어보았다.

💡queue에 append를 할 수록 트리형태가 되기 때문에 queue가 다 비워질 때 까지 pop()을 하면 안되고 queue의 길이까지만 pop을 해주어야 한다.

💡queue와 list 등에 있는 내장함수 count함수를 이용하여 target의 개수만을 세어준다.