프로그래머스 | dfs/bfs | 타겟 넘버

2026.04.01

아예 왼오를 나눠서 더하는게 더 좋았을 것 같기도 하다

같은 dfs지만 이 코드가 더 간단함

def dfs(curr, numbers, target, i):
    # 0 > 0-4=-4 > -4-1=-5 > -5-2=-7 > -7-1=-8
    if i == len(numbers):
        if curr == target:
            return 1
        return 0
    
    left = dfs(curr-numbers[i], numbers, target, i+1)
    right = dfs(curr+numbers[i], numbers, target, i+1)
    
    return left + right
    
    
def solution(numbers, target):
    # dfs 접근법
    # 시작 값 0에서 좌우로 -1, +1 나눠서 들어가는 것
    
    return dfs(0, numbers, target, 0)

 

---

2026.04.01

itertools를 사용하면 훨씬 문제를 간단하게 풀긴함

from itertools import product

def solution(numbers, target):
    # 결국 모든 조합을 계산해보고 target이랑 같은 수를 return 해야 한다
    # 각 숫자 앞에 -1 혹은 1을 곱해서 다 더하면 되는 구조
    # 그 모든 조합을 어떻게 셀 것인가
    minus_plus = [-1, 1]
    answer = 0
    for perm in product(minus_plus, repeat=len(numbers)):
        # [-1,1,-1,1,1]
        number = 0
        for idx, p in enumerate(perm):
            number += p * numbers[idx]
        if number == target:
            answer += 1
    return answer

---

사실 dfs/bfs로 분류되어있지 않으면 그래프로 접근해서 풀 생각을 안했을 것 같기도 하다 ,, ㅠ

그러나 어쨌든 크게 어렵지 않게 잘 접근함

global 변수도 잘 쓰는게 중요하다

answer = 0
def dfs(numbers, curr, target, result, depth):
    global answer
    if depth == len(numbers):
        if result == target:
            answer += 1
        return
    
    dfs(numbers, curr+1, target, result+numbers[curr], depth+1)
    dfs(numbers, curr+1, target, result-numbers[curr], depth+1)
    
    
def solution(numbers, target):
    # answer = 0
    dfs(numbers, 0, target, 0, 0)
    return answer