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

문제

---

 https://school.programmers.co.kr/learn/courses/30/lessons/43165

문제유형 : BFS, DFS

---

BFS 풀이법

---

def solution(numbers, target):
    answer = bfs(numbers, target)
    return answer

def bfs(numbers, target):
    answer = 0
    sums = [0] 
    
    for num in numbers:
        tmp = []
        for s in sums:
            tmp.append(s + num)
            tmp.append(s - num)
        sums = tmp
        
    for s in sums:
        if s == target:
            answer += 1
    
    return answer

•  `sums = []`, `tmp = [0]` 로 초기화했다가 에러가 발생했다.
• `for s in sums` 에서 빈 배열에 접근하므로 인덱스 에러가 발생했을 것이다

DFS 풀이법

---

def solution(numbers, target):
    answer = dfs(numbers, target, 0)
    return answer

def dfs(numbers, target, depth):
    answer = 0
    # 탈출조건
    if len(numbers) == depth:
        if sum(numbers) == target:
            return 1
        else:
            return 0
    else:
        answer += dfs(numbers, target, depth+1)
        numbers[depth] *= -1
        answer += dfs(numbers, target, depth+1)
        return answer
        
        def solution(numbers, target):

 

다시 한 번 풀어봄

def solution(numbers, target):
    answer = 0
    answer = dfs(numbers, target, 0, 0)
    return answer

def dfs(numbers, target, depth, sum):
    cnt = 0
    
    if depth == len(numbers):
        if sum == target:
            #print("탈출=[1]-----------------------")
            return 1
        else:
            #print("탈출=[0]-----------------------")
            return 0
    else:
        a, b = numbers[depth], (numbers[depth]*-1)
        #print(f"depth={depth} | sum={sum} | a,b={a,b} | cnt={cnt}")
        
        cnt += dfs(numbers, target, depth+1, sum+a)
        #print(f"depth={depth} | sum={sum} | a={a} | cnt={cnt}")
        
        cnt += dfs(numbers, target, depth+1, sum+b)
        #print(f"depth={depth} | sum={sum} | b={b} | cnt={cnt}")
        
        #print(f"재귀 out | cnt={cnt}")
        return cnt