[dfs, bfs / 프로그래머스] 43175번 : 타겟 넘버

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

처음에는 왜 dfs,bfs를 사용하는 건지 이해가 가지 않았지만, 생각해보니 +이든 -이든 숫자들이 차례로 진행되기 때문에 이는 dfs로 진행해야겠다고 생각했다 

 

문제 이해

탐색이 끝난 후 수의 합을 target과 비교해야하므로 이를 num_sum을 이용해서 진행하고, 숫자도 하나씩 움직여야하므로 idx 변수도 이용한다

1. numbers 내부에 있는 숫자라면 그 숫자를 num_sum에 더하고, 뺀 값으로 dfs를 진행한다

2. numbers에 있는 모든 원소들을 다 사용해야하므로 마지막 인덱스까지 사용했는지 확인하고, 숫자의 총 합이 target과 같으면 갯수 +1 해준다. idx + 1을 통해 숫자도 오른쪽으로 한 칸 옮겨 준다

 

참고한 블로그

 

- 정답 풀이 :

answer = 0
def dfs(idx, num_sum, target, numbers):
    global answer
    if idx == len(numbers) and num_sum == target:
        answer += 1
        return True
    if idx != len(numbers):
        dfs(idx + 1, num_sum + numbers[idx], target, numbers)
        dfs(idx + 1, num_sum - numbers[idx], target, numbers)
            
def solution(numbers, target):  
    dfs(0, 0, target, numbers)
    
    return answer

 

- 시도해본 풀이 :

정확하지는 않지만, 인덱스에 대한 설정이 없어서 틀렸던 것 같다

 

numbers에서 원소 하나씩 꺼낸 다음 그것을 더했을 때와 - 했을 때의 값을 넣어서 진행한다 

진행하다가 모든 수의 합이 target과 같으면 함수를 멈춘다(일단 모든 원소를 다 사용해야하는데 이렇게 하면 모든 원소를 다 사용하지 않아도 수의 합이 target이 되는 경우가 있어서 이렇게 작성하면 안될 것 같다)

answer = 0
def dfs(numbers, num_sum, target):
    global answer
    diff = [1 , -1]
    if num_sum == target:
        answer += 1
        return True
    
    if len(numbers) > 0:
        x = numbers.pop(0)
        for i in range(2):
            nx = x * diff[i]
            num_sum += nx
            dfs(numbers, num_sum, target)
            num_sum -= nx
            
def solution(numbers, target):    
    dfs(numbers, 0, target)
    
    return answer