[ Lv 2 ] 타겟 넘버

- bfs로 구현, 왼쪽에서 순차적으로 진행하면서 현재 요소의 값이 +일때와 , -일때 각각의 누적합을 큐에 저장

- 마지막 요소까지 방문한다면 그만 하되, target과 누적합이 같다면 개수 1 증가

- 전체 개수 리턴해주는 방식으로 구현

from collections import deque

def bfs(numbers, target):
    queue = deque()
    queue.append([numbers[0], 1])
    queue.append([-numbers[0], 1])
    answer = 0
    while queue:
        currentSum, idx = queue.popleft()
        if idx == len(numbers):
            if currentSum == target:
                answer += 1
            continue
        queue.append([currentSum + numbers[idx], idx+1])
        queue.append([currentSum - numbers[idx], idx+1])
    
    return answer
            
def solution(numbers, target):
    return bfs(numbers, target)

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges