배열 leaves에는 모든 계산 결과가 담겨있다.
맨 아래 for문에서는 target 값과 비교해서 같은 경우를 더해 출력한다.
#BFS 풀이
def solution(numbers, target):
answer = 0
leaves = [0]
for num in numbers:
tmp=[]
for parent in leaves:
tmp.append(parent+num)
tmp.append(parent-num)
leaves = tmp
print(leaves)
for leaf in leaves:
if leaf == target:
answer += 1
return answer
#BFS 풀이
def solution(numbers, target):
a=[0]
for i in numbers:
b=[]
for j in a:
b.append(j+i)
b.append(j-i)
a=b
return a.count(target)
재귀를 사용하여 문제를 해결한다.
변수 depth를 통해 탐색 중인 트리의 깊이를 알 수 있고,
트리 끝에 도착했다면, number 값을 모두 더한 값을 비교한다.
#DFS 풀이
def solution(numbers, target):
answer = DFS(numbers, target, 0)
return answer
def DFS(numbers, target, depth):
answer = 0
if depth == len(numbers):
if sum(numbers) == target:
return 1
else: return 0
else:
answer += DFS(numbers, target, depth+1)
numbers[depth] *= -1
answer += DFS(numbers, target, depth+1)
return answer
DFS 손코딩으로 완벽히 이해는 안됐지만 어느정도 DFS 식으로 하나씩 비교하여 값을 변경하며 풀리는 과정은 감이 생겼다.