DFS(깊이 우선 탐색) Programmers <타겟 넘버> 문제 풀이

DFS

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다.

numbers=[4,1,2,1]인 경우를 예시로 트리를 그리면 다음처럼 그릴 수 있다.

(0,0)에서 첫번째는 index이고 두번째는 연산한 후의 값이다.

연산을 모두 마쳤을 때 target 값인 4를 가지는 경우는 2가지이므로 return 값은 2이어야 한다.

재귀함수를 이용하여 풀었다.

def solution(numbers, target):
    current_sum = 0
    index = 0
    def dfs(index, current_sum):
        
        # numbers 끝까지 갔을 때
        if index == len(numbers):
            if current_sum == target:
                return 1 
            else:
                return 0
        
        # 숫자를 더하는 경우
        add = dfs(index + 1, current_sum + numbers[index])
        # 숫자를 빼는 경우
        subtract = dfs(index + 1, current_sum - numbers[index])
        
        return add + subtract
    answer = dfs(index,current_sum)

    return answer

---

글로벌소프트웨어캠퍼스와 교보DTS가 함께 진행하는 챌린지입니다.