[프로그래머스 Lv.2] 타겟 넘버

# BFS
from collections import deque

def solution(numbers, target):
    answer = 0
    
    queue = deque()
    
    queue.append((numbers[0],0))
    queue.append((-numbers[0],0))
    
    while queue:
        v, index = queue.popleft()
            
        index += 1
        
        if index < len(numbers):
            queue.append((v+numbers[index],index))
            queue.append((v-numbers[index],index))
        else:
            if v == target:
                answer += 1
    
    return answer

#DFS
def solution(numbers, target):
    global answer
    answer = 0
    
    def dfs(value, index):
        global answer
            
        if index+1 <= len(numbers):
            dfs(value-numbers[index],index+1)
            dfs(value+numbers[index],index+1)
        else:
            if value == target:
                answer += 1
    dfs(0,0)
    
    return answer

이번 문제는 주어진 n개의 정수를 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는 경우의 수를 구하는 문제이다.

 

처음에 이 문제를 접근할 때는 모든 경우의 수를 구하는 방법을 피하려고 했었는데, 제한사항에 주어진 숫자의 개수가 20개로 제한되어 있어서 완전 탐색으로 풀어도 상관없을 것 같다고 판단이 되었다.(2^20 = 1,048,576)

 

따라서 DFS와 BFS를 사용하여 모든 경우의 수를 탐색하고, 모든 경우의 수 중에서 target 값과 같을 때 answer를 +1 해주는 방식으로 풀이해주었다.

 

2차원 배열을 사용한 DFS/BFS 문제에 익숙해져있던 탓에 문제를 풀이하는데 시간이 오래걸렸는데, 이러한 탐색 유형의 문제도 많이 풀어봐야겠다고 느낄 수 있었던 문제였다 :)