[DFS] 프로그래머스_타겟넘버

깊이/너비 우선 탐색(DFS/BFS) >타겟 넘버

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

문제 설명

풀이 과정

Wrong Access

입출력 예시가

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

이것 딱 하나여서 처음에는 하나의 숫자 n개를 가지고 target이 나오는 조합을 찾으라는건가 싶었다.
그래서 이렇게 target이 나올 수 있는지부터 찾아보려고 방정식을 구하다가 문제를 다시 정독했더니 한개의 정수 n개로 target을 만들라고 하지 않았다는 점, 굳이 numbers[] 로 입력이 주어진다는 점에서
numbers[]는 0이 아닌 정수들의 집합이라고 생각하고 설계를 했다.

Correct Access

이렇게 numbers에 속한 모든 숫자들을 더하고, 뺄때 모든 경우를 다 봐야했기때문에 재귀함수를 만들게되었다. 부모노드에서 자식노드가 더이상 안보일때까지 계에에에속 파고들면서 내려갔다가 올라오니까 DFS 방식으로 풀어야한다고 생각했다.

코드

result = set()


def solution(numbers, target):
    route = [0 for _ in range(len(numbers))]

    # print(numbers)

    dfs(numbers, 0, route, target, 0)

    print(result)

    answer = len(result)
    return answer


def dfs(numbers, idx, route, target, sum):
    if idx == len(numbers):
        if sum == target:
            str_route = ''.join(map(str, route))
            # print(str_route)
            result.add(str_route)
        return

    route[idx] = -1
    add_num = route[idx] * numbers[idx]
    dfs(numbers, idx + 1, route, target, sum + add_num)

    route[idx] = 1
    add_num = route[idx] * numbers[idx]
    dfs(numbers, idx + 1, route, target, sum + add_num)