프로그래머스[Python] - 타겟 넘버 풀이

풀이

Permutation형식으로 복잡하게 접근하기 보다, 깊이 우선 탐색(dfs) 너비 우선 탐색(bfs)를 통해 numbers의 모든 값에 하나하나 계산해가면서 풀어나가는 방향을 잡았다.

 

특히 문제에서 덧셈, 뺄셈만 이용해서 target 값에 도달하라고 했으므로, 초기 경우의 값이 number[0]와 -number[0] 이 두가지를 베이스로 dfs와 bfs구조를 만들어 나가면 된다.

 

dfs의 경우 재귀이기 때문에 재귀 부분을 먼저 짠 후, if를 통해 종료 조건을 잡아주면 된다.

from collections import deque

## 재귀함수를 이용한 dfs 풀이
def dfs(numbers, target, depth):
    answer = 0
    if(len(numbers) == depth) :
        if sum(numbers) == target:
            return 1
        else :
            return 0
    
    answer += dfs(numbers, target, depth + 1)
    numbers[depth+1] *= -1
    answer += dfs(numbers, target, depth + 1)
    return answer

## Queue를 이용한 bfs 풀이
def bfs(numbers, target):
    n = len(numbers)
    queue = deque()
    answer = 0
    
    queue.append([numbers[0], 0])
    queue.append([-1*numbers[0], 0])
    
    while queue:
        num, inx = queue.popleft()
        
        if(inx == n - 1):
            if(num == target):
                answer += 1
            
        else:
            queue.append([num + numbers[inx + 1], inx + 1])
            queue.append([num - numbers[inx + 1], inx + 1])
    return answer
            

def solution(numbers, target):
    answer = dfs(numbers, target, 0)
    answer = bfs(numbers, target)
    return answer