DFS/BFS 개념

📌 프로그래머스

👉타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3

DFS 풀이

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

다른사람의 풀이입니다

BFS 풀이

import collections

def solution(numbers, target):
    answer = 0
    stack = collections.deque([(0, 0)])
    while stack:
        print(stack)
        current_sum, num_idx = stack.popleft()
        print(current_sum , num_idx)
        if num_idx == len(numbers):
            if current_sum == target:
                answer += 1
        else:
            number = numbers[num_idx]
            stack.append((current_sum+number, num_idx + 1))
            stack.append((current_sum-number, num_idx + 1))

    return answer

print(solution([1,1,1,1,1,] , 3))