📢 "타겟 넘버" 문제

프로그래머스 문제 링크

🔎 풀이

사용 언어 : python

출처

💡 BFS

너비 우선 탐색 (BFS)
: 현재 정점에 연결된 가까운 정점들부터 탐색
: 큐를 이용하여 구현
: 최단 거리 문제에서 자주 사용

• 수평적으로 결과를 추가

def solution(numbers, target):
    answer = 0
    result = [0]
    for x in numbers:
        test = []
        for y in result:
            test.append(x+y)
            test.append(y-x)
        result = test
    return result.count(target)

💡 DFS

깊이 우선 탐색 (DFS)
: 현재 정점에서 갈 수 있는 점까지 들어가면서 탐색
: 스택 또는 재귀함수로 구현

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    
    def dfs(index,result):
        if index == n:
            if result == target:
                nonlocal answer
                answer+=1
            return
        else:	
            dfs(index+1,result+numbers[index]) # 재귀함수
            dfs(index+1, result-numbers[index])
    dfs(0,0)
    return answer