프로그래머스 타겟 넘버, DFS,BFS 탐색

문제

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

target을 만드는 배열 합이 나오는 방법의 수를 구하는 문제
각 배열 원소가 + 혹은 - 일 경우를 따지며 DFS,BFS 탐색으로 풀 수 있다.

---

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
    for leaf in leaves:
        if leaf == target:
            answer += 1
    return answer

DFS

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

def DFS(numbers, target, depth):
    answer = 0
    if depth == len(numbers):
        print(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방식이 내가 하려 했던 방법과 유사했다.
요즘 재귀구조가 아직 너무 미숙하다보니 그래프관련 알고리즘을 풀어내는 것에 어려움을 겪고 있다 ㅠ

---

풀이 출처

https://velog.io/@timointhebush/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-DFS-BFS-Python