프로그래머스_고득점kit_우선탐색_타겟넘버

풀이

class Solution {
    int count = 0; // 정답 개수를 저장하는 변수

    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0); // DFS 탐색 시작
        return count;
    }

    private void dfs(int[] numbers, int target, int index, int sum) {
        // 1. 모든 숫자를 다 사용한 경우
        if (index == numbers.length) {
            if (sum == target) { // 목표 숫자와 같다면
                count++; // 정답 개수 증가
            }
            return; // 재귀 종료
        }

        // 2. 현재 숫자를 더하는 경우
        dfs(numbers, target, index + 1, sum + numbers[index]);

        // 3. 현재 숫자를 빼는 경우
        dfs(numbers, target, index + 1, sum - numbers[index]);
    }
}

---

개념정리

 

❓깊이우선탐색(DFS)

✔️한방향으로 끝까지 가보고 , 다시 돌아와서 다른 방향도 탐색하는 방식

✔️트리 형태로 모든 경우의 수를 탐색

✔️함수 안에서 자기 자신을 호출하는 방식으로 동작(재귀)