[프로그래머스/파이썬] 타겟 넘버

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

프로그래머스

BFS/DFS 연습용 문제이다

 

예시가 4,1,2,1이라고 하면,

 

4 -> 5 or 3 에서

 

5 -> 6 or 4 와 3 -> 4 or 2 ,,,

 

와 같은 식으로 갈 수 있다.

from collections import deque
def solution(numbers, target):
    answer = 0

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