[프로그래머스 lv 2] 타겟 넘버(깊이/너비 우선 탐색(DFS/BFS))

아이디어 : 경우의 수는 더하거나(+), 빼거나(-) 둘 중 하나. 그러면 트리 형식처럼 만약 2개의 숫자가 있다면 ++, --, -+, +-을 모두 고려하는 그런 방식이 될 수 있을 것 같다. -> 이렇게 하려면 더하는 경우와 빼는 경우를 각각 따로 탐색해야 한다. 즉, 따로 돌아가게 한다는 점에서 재귀함수를 써야 할것 같기도 한데... 즉, DFS 문제인것 같기는 하다.

 

global answer
answer = 0

def calculate(sign, numbers, cal_num, count, target):
    global answer
    if count < 1:
        if cal_num==target:
            answer+=1
        return None
    else:
        count -= 1
        if sign == "+":
            cal_num += numbers[count]
        elif sign == "-":
            cal_num -= numbers[count]

        calculate("+",numbers,cal_num,count,target)
        calculate("-",numbers,cal_num,count,target)

def solution(numbers, target):
    global answer
    cal_num = 0
    count = len(numbers)
    
    calculate("+",numbers,cal_num,count,target)
    calculate("-",numbers,cal_num,count,target)
    answer = answer/2 
    
    return answer