프로그래머스 DFS/BFS LV2

타겟 넘버

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
//////////////////////////
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
//////////////////////////
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
numbers / target / return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2

입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4

과정

def solution(numbers, target):
    answer = 0
    Q=[]
    Q.append([numbers[0],0])
    Q.append([numbers[0]*-1,0])
    
    while Q :
        tmp, idx = Q.pop(0)
        idx+=1
        if idx < len(numbers):
            Q.append([tmp+numbers[idx],idx])
            Q.append([tmp-numbers[idx],idx])
        else :
            if target == tmp : answer+=1
                
                
    return answer

bfs dfs 에대한 개념과 어색함 때문에 결국 구글링을 통해서 힌트를 얻었다.
BFS는 queue를 DFS는 stack을 사용한다는 것을 알게 되었다.

그래프는 {1:[1,-1],2:[1->1,1->-1,-1->1,-1 ->-1],.....}
이런식으로 순회한다.

이를 이용해 리스트에 합쳐진 값과 깊이 수준을 같이 묶어서 넣어서 깊이의 끝에 도달했을때의 합이 맞냐 안맞냐로 구분하는 코드를 짰다.
하지만 시간 초과 문제로인해 실패

코드

from collections import deque

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

큐를 deque로 바꾸니 해결되었다.