[프로그래머스][BFS] 타겟 넘버

문제

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 함수를 작성해주세요.

 

 

 

 

내 생각

1. BFS문제로 분류되어 있길래 큐를 사용한 BFS 먼저 생각했다. 

deque 안에 인덱스를 합과 같이 넣으면 원하는 값을 더 쉽게 구할 수 있다고 생각했다.

그 이유는 tmp 값의 다음 값(다음 인덱스)에 위치한 numbers의 값을 + 와 -를 계산하기 때문!

즉, 위치를 편하게 알 수 있으므로 같이 넣어주는게 낫다고 생각한다.

종료 조건은 큐의 값이 없을 때까지 반복한다.

그리고 인덱스 번호가 numbers의 길이와 같고, tmp 값이 target 넘버와 같다면 방법 + 1이 된다.

간단하다 !

그리고 큐에 추가할 때 인덱스 번호를 늘려줘야 한다는 것을 잊지 말자 !

 

2. 스택을 사용한 DFS 

큐 대신 스택을 사용한거 빼고는 그대로다 !

 

 

 

내 코드

1. BFS

from collections import deque

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

 

2. DFS

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