[Python] 타겟 넘버 - DFS/BFS

문제

해당 문제 링크

정답 및 풀이

BFS

배열 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)

DFS

재귀를 사용하여 문제를 해결한다.
변수 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 식으로 하나씩 비교하여 값을 변경하며 풀리는 과정은 감이 생겼다.

결과

코드 참고 사이트 (1)

코드 참고 사이트 (2)