[python] 프로그래머스_타겟넘버 (DFS&BFS)

문제

 

풀이

BFS 를 이용하여 풀 수 있다. 다음 수를 더하고 빼는 경우 두가지를 모두 큐에 넣으면서 BFS를 진행시키고 target 과 동일한 경우에 카운트해준다.

 

코드

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer