[프로그래머스] 타겟 넘버 (Python)

프로그래머스 문제 풀이 - 깊이/너비 우선 탐색 (DFS/BFS)

📰 문제

문제 확인 🏃

💡 입출력 예제

[1, 1, 1, 1, 1], 3

>> 5

[4, 1, 2, 1], 4

>> 2

해설.	
+4+1-2+1 = 4
+4-1+2-1 = 4

💬 풀이

🎵 첫번째 풀이

count = 0

def solution(numbers, target):
    dfs(numbers, target, 0, 0)
    return count


def dfs(numbers, target, idx, sum):

    global count
    if idx == len(numbers):
        if sum == target:
            count += 1
        return
    
    dfs(numbers, target, idx+1, sum-numbers[idx])
    dfs(numbers, target, idx+1, sum+numbers[idx])

🎵 두번째 풀이

from collections import deque

def solution(numbers, target):
    queue = deque()

    queue.append(numbers[0])
    queue.append(-numbers[0])

    idx = 1

    while idx < len(numbers):

        for _ in range(len(queue)):

            num = queue.popleft()

            queue.append(num + numbers[idx])
            queue.append(num - numbers[idx])

        idx += 1

    return queue.count(target)

✒️ 생각