[level 2] 타겟넘버

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

프로그래머스

#bfs
def solution(numbers,target):
    sup=[0]
    cnt=0
    for n in numbers:
        temp=[]
        for i in sup:
            temp.append(i+n)
            temp.append(i-n)
        sup=temp
    return sup.count(target)

#dfs
def dfs(numbers, target, idx, values):     # idx : 깊이 / values : 더하고 뺄 특정 leaf 값 
	
    global cnt
    cnt = 0 
	
    # 깊이가 끝까지 닿았으면 
    if idx == len(numbers) & values == target : 
    	cnt += 1
        return 
  
    # 끝까지 탐색했는데 sum이 target과 다르다면 그냥 넘어간다
    elif idx == len(numbers) : 
    	return 
    
    # 재귀함수로 구현 
    dfs(numbers, target, idx+1, values + numbers[idx])   # 새로운 value 값 세팅   
    dfs(numbers, target, idx+1, values - numbers[idx])
 
 def solution(numbers, target) : 
 	
    global cnt
    dfs(numbers, target, 0, 0)
    
    return cnt

핵심포인트

✅ 가장 main idea는 +, - 부호에 따른 각 숫자에서 2가지 경우의 수가 생산된다는 것이다. 따라서 numbers의 각 숫자에 따라 2가지 경우로 자손을 뻗을 수 있게되고, 모든 경우의 수를 탐색하는 bfs/dfs 문제가 된다.