[프로그래머스] 타겟 넘버 | DFS, BFS | Level.2 | JAVA

📌 문제

 

프로그래머스

 

🌞 정답 코드

class Solution {
    int answer = 0, sum = 0;
    public void dfs(int[] numbers, int target, int index, int sum){
        index++;
        if (index==numbers.length){
            if(sum==target) answer++;
            return;
        }
        
        else {
            dfs(numbers, target, index, sum+numbers[index]);
            dfs(numbers, target, index, sum-numbers[index]);
        }
    }
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, -1, 0);
        
        return answer;
    }
}

 

✅ dfs 메서드에 따른 변수의 변화 

예시: numbers = [1, 2, 3], target = 3

1. 초기 호출
   • dfs(numbers, target, -1, 0)
   • 상태:
     • index = -1
     • sum = 0
     • answer = 0
2. 첫 번째 dfs 단계
   
   • index++ → index = 0
   • 호출 : dfs(numbers, target, 0, 0+1)
   • 상태:
     • index = 0
     • sum = 1
3. 두 번째 dfs 단계
   • index++ → index = 1
   • 호출 : dfs(numbers, target, 1, 1+2)
   • 상태 :
     • index = 1
     • sum = 3
4. 세 번째 dfs 단계
   • index++ → index = 2
   • 호출 : dfs(numbers, target, 2, 3+3)
   • 상태:
     • index = 2
     • sum = 6
   • 기저 조건 확인: sum == target → answer++ (answer = 1)
5. 네 번째 DFS 단계 (모든 숫자를 사용한 상태)
   • index++ → index = 3
   • 호출 : dfs(numbers, target, 3, 6)
   • 상태 :
     • index = 3
     • sum = 6
     • 기저 조건 확인: sum != target → answer = 0
6. 돌아가기 : 세 번째 dfs 단계로  
   • 호출 : dfs(numbers, target, 2, 3-3)
   • 상태:
     • index = 2
     • sum = 0
7. 네 번째 dfs 단계 (모든 숫자를 사용한 상태)  
   • index++ → index = 3
   • 호출 : dfs(numbers, target, 2, 0)
   • 상태:
     • index = 3
     • sum = 0
   • 기저 조건 확인: sum != target → answer = 0
8. 돌아가기 : 두 번째 dfs 단계로 
   
   • 호출 : dfs(numbers, target, 1, 1 - 2)
   • 상태:
     • index = 1
     • sum = -1
9. 세 번째 dfs 단계 
   • index++ → index = 2
   • 호출 : dfs(numbers, target, 2, -1 + 3)
   • 상태:
     • index = 2
     • sum = 2
10. 네 번째 dfs 단계 (모든 숫자를 사용한 상태) 
    
    • index++ → index = 3
    • 호출 : dfs(numbers, target, 3, 2)
    • 상태:
      • index = 3
      • sum = 2
    • 기저 조건 확인: sum != target → answer = 0
11. 돌아가기 : 첫 번째 dfs 단계로
    • 호출 : dfs(numbers, target, 0, 0 - 1)
    • 상태:
      • index = 0
      • sum = -1
12. 첫 번째 dfs 단계
    
    • index++ → index = 1
    • 호출 : dfs(numbers, target, 1, -1+2)
    • 상태:
      • index = 1
      • sum = 1