[DFS & BFS] 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

해당 문제는 numbers의 부호를 모두 탐색해야 하는 완전 탐색 문제입니다.

보통 DFS는 완전 탐색에 사용되고, BFS는 최단 거리 계산에 사용되기 때문에 "타겟 넘버" 문제는 DFS로 해결할 수 있습니다.

 

numbers의 모든 값들에 대하여 +, -를 했을 때, 그 합이 target 값과 일치하는지만 확인하면 되기때문에 다른 완전 탐색 문제보다는 쉽게 해결했습니다.

def dfs(numbers, idx, sign, target, cnt):
    number = numbers.copy()
    if not sign:
        number[idx] = -number[idx]
    
    if idx < len(numbers) - 1:
        cnt = dfs(number, idx + 1, False, target, cnt)
        cnt = dfs(number, idx + 1, True, target, cnt)
    else:
        if sum(number) == target:
            cnt += 1
    
    return cnt
        
def solution(numbers, target):
    answer = 0
    
    answer += dfs(numbers.copy(), 0, False, target, 0)
    answer += dfs(numbers.copy(), 0, True, target, 0)
    
    return answer

+, - 경우에 대하여 numbers를 완전 탐색할 수 있도록 dfs()함수를 정의하여 사용합니다.

sign에 따라 +, -를 결정하고 dfs()를 재귀 호출하면 간단하게 완성시킬 수 있습니다.