프로그래머스_타겟 넘버

문제

풀이

처음 문제를 봤을 때 이게 왜 DFS/BFS 문제야? 하고 의아해했다. 문제만 놓고 보면 처음에는 그냥 그리디 문제인가 싶었지만 찬찬히 생각해보니 DFS/BFS 방식으로 풀 수 있겠구나 싶었다.
우선, 연산의 개수는 + 와 - 두가지 밖에 없다. 그렇다면 각 매번 배열의 각 인덱스들을 지나칠 때 마다 결과 값이 2가지로 나뉜다는 것이고 이걸 그림으로 그려보면 다음과 같다.
예시 1번을 그려보면

위 그림처럼 되는데 여기서 target 넘버와 같은 결과값은 내는 과정들만 찾아내면 되는 문제이다.

풀이 코드

def solution(numbers, target):
    global answer
    answer = 0
    n = len(numbers)
    def dfs(cnt, result):
        global answer
        if cnt == n:
            if result == target:
                answer += 1
                return
        else:
            dfs(cnt+1, result + numbers[cnt])
            dfs(cnt+1, result - numbers[cnt])
    
    
    dfs(0,0)
    
    return answer