[Java] 타겟넘버

DFS (Depth-Fisrt Search, 깊이우선탐색)

문제

• 사용할 수 있는 숫자가 담긴 배열 numbers
  • int[] numbers
• 타겟 넘버 target이 매개변수로 주어질 때
  • int target
• 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
  • class Solution {}

정답 코드

import java.util.*;

class Solution {
	// numbers는 숫자가 담긴 배열
    // target은 숫자가 담긴 매개변수
    public int solution(int[] numbers, int target) {
    	// index와 cur는 0을 초기값으로 return한다.
        return dfs(numbers, 0, target, 0);
    }
     // dfs 함수를 호출하여 타겟 값을 만드는 경우의 수를 계산
    int dfs(int[] numbers, int index, int target, int cur) {
        // 모든 숫자를 다 사용한 경우
        if(index == numbers.length) {
            // 현재 값이 타겟 값과 같으면 1을 반환 (경우의 수 1개)
            // 그렇지 않으면 0을 반환
            return (cur == target ? 1 : 0);
        }
        
        // 깔끔하게 return값을 작성하기 위해 int sum을 초기화해준다.
        int sum = 0; 
        
        // cur에 numbers[index]를 더하는 경우와 빼는 경우를 구해준다.
        // 현재 숫자를 더하는 경우
        sum += dfs(numbers, index+1, target, cur+numbers[index]);
        // 현재 숫자를 빼는 경우
        sum += dfs(numbers, index+1, target, cur-numbers[index]);
        
        // 모든 경우의 수를 더해서 반환
        return sum;
    }
}

깊이 우선 탐색(DFS, Depth-First Search)을 사용하여 주어진 숫자 배열에서 덧셈과 뺄셈을 통해 특정 타겟 값을 만드는 모든 경우의 수를 찾는 것입니다.

상세 설명

1. public int solution(int[] numbers, int target):

   • 이 함수는 문제를 해결하기 위한 메인 함수입니다. 숫자 배열 numbers와 목표 값 target을 입력받습니다.
   • dfs 함수를 호출하여 모든 경우의 수를 계산하고 그 결과를 반환합니다.

2. int dfs(int[] numbers, int index, int target, int cur):

   • dfs는 재귀 함수로, 깊이 우선 탐색을 통해 가능한 모든 경우를 탐색합니다.
   • index는 현재 탐색 중인 숫자의 인덱스입니다.
   • target은 목표 값입니다.
   • cur는 현재까지의 계산 값입니다.

3. if(index == numbers.length):

   • 모든 숫자를 다 사용한 경우입니다.
   • 현재 계산 값 cur이 목표 값 target과 같은지 확인합니다.
   • 같으면 1을 반환하여 이 경로가 유효한 경우의 수임을 나타냅니다.
   • 다르면 0을 반환하여 이 경로는 유효하지 않음을 나타냅니다.

4. int sum = 0;:

   • 가능한 모든 경우의 수를 합산하기 위한 변수입니다.

5. sum += dfs(numbers, index + 1, target, cur + numbers[index]);:

   • 현재 숫자를 더하는 경우를 탐색합니다.
   • 다음 인덱스로 넘어가며, 현재 값에 현재 인덱스의 숫자를 더합니다.

6. sum += dfs(numbers, index + 1, target, cur - numbers[index]);:

   • 현재 숫자를 빼는 경우를 탐색합니다.
   • 다음 인덱스로 넘어가며, 현재 값에 현재 인덱스의 숫자를 뺍니다.

7. return sum;:

   • 가능한 모든 경우의 수를 합산하여 반환합니다.

이 방식은 각 숫자에 대해 더하기와 빼기를 시도하며 모든 가능한 경우를 재귀적으로 탐색하여 목표 값을 만들 수 있는 모든 경우의 수를 계산합니다.