[프로그래머스] DFS/BFS - 타겟 넘버

🎯 programmers : 깊이/너비 우선 탐색 - 타겟 넘버

---

🤔 나의 풀이

📌 문제

- 프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색 > Level 2 타겟 넘버

📌 날짜

2021.03.09

📌 시도 횟수

5 try

💡 Code

answer = 0
def solution(numbers, target):
    max_idx = len(numbers) - 1

    def dfs(idx, num, cur_sum):  # -1, 0, 0 부터 시작해야됨
        global answer
        cur_sum += num
        if idx == max_idx:
            if cur_sum == target:
                answer += 1
            return

        idx += 1
        num = numbers[idx]
        dfs(idx, num, cur_sum)
        dfs(idx, -num, cur_sum)

    dfs(-1, 0, 0)
    return answer

💡 문제 해결 방법

• 

- dfs 재귀를 실행할 때마다 idx(인덱스) 값을 1씩 늘렸다. (마치 for문처럼 동작한다)
- 만약 현재 idx가 len(numbers)-1 가 되었다면 현재까지의 path를 모두 더한
cur_sum이 target과 일치하는지 검사한다.

- 참고로 dfs를 시작할 때 주는 루트 값의 idx를 -1로 주어
다음 재귀때부터 (idx + 1 = 0) 0이 되어 정상적으로 동작하도록 설정해주었다.

💡 새롭게 알게 된 점

- 

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 

위의 코드를 좀 더 깔끔하게😄

answer = 0

def solution(numbers, target):
    global answer
    answer = 0

    def dfs(cur_sum, idx):
        global answer
        if idx == len(numbers):
            if cur_sum == target:
                answer += 1
            return

        dfs(cur_sum - numbers[idx], idx + 1)
        dfs(cur_sum + numbers[idx], idx + 1)

    dfs(0, 0)
    return answer