[프로그래머스] 타겟 넘버 (DFS 깊이 우선 탐색) - Python

1. 문제

문제 보러가기

2. 나의 풀이

def solution(numbers, target):
    answer = 0
    
    def dfs(number, total):
        nonlocal answer
        
        if number == len(numbers):
            if total == target: answer += 1
            return
        
        dfs(number + 1, total + numbers[number])
        dfs(number + 1, total - numbers[number])
        
    dfs(0, 0)

    return answer

3. 풀이 과정

숫자를 양수와 음수로 바꾼 후 더하는 과정을 전부 거치고 타겟 넘버와 동일한 개수를 구한다.
모든 경우를 짚어야 하기 때문에 완전 탐색을 이용해야 한다.

재귀 함수로 문제를 풀 때는 문제를 어떻게 쪼갤지 고민하기 전에 어떤 결과를 반환할 것인지 정해야 한다.
DFS 함수를 실행하고 나오는 결과는 모든 숫자를 다 계산했을 때 원하는 숫자가 나왔는가에 대한 정보이다.

그리고 양수와 음수 두 가지 경우를 살펴보아야 하기 때문에 DFS 함수를 두 번 선언한다.

def dfs(number, total):  # 1
    nonlocal answer  # 2
        
    if number == len(numbers):  # 3
        if total == target: answer += 1  # 3-1
        return  # 3-2
        
    dfs(number + 1, total + numbers[number])  # 4
    dfs(number + 1, total - numbers[number])

1. 현재 더해진 숫자 개수를 number, 숫자 합계를 total이라고 매개변수를 정한다.

2. dfs 함수에서 사용될 answer 는 함수 밖에서 선언되었기 때문에 nonlocal이라고 재선언한다.

3. 현재 더해진 숫자 개수가 전체 숫자의 개수와 동일하다면
   3-1. 숫자 합계가 타겟 넘버와 동일하면 answer 에 개수 하나를 추가한다.
   3-2. 동일하지 않다면 그대로 dfs 함수를 끝낸다.

4. 현재 더해진 숫자 개수가 전체 숫자의 개수와 다르다면,
   숫자 하나를 더하고 숫자 합계에서 해당 위치의 숫자를 더하거나 빼는 dfs 함수를 선언한다.

그림으로 표현하면 다음과 같다.