프로그래머스 타겟 넘버 깊이/너비 우선 탐색(DFS/BFS)

 

풀이법

n개의 음이 아닌 정수 숫자를 적절히 더하거나 빼야한다 

처음에는 모든수를 검색해야 겠다는 생각은 했지만 DFS로 풀어야 겠다는 생각은 하지 못했다.

DFS는 점화식과 종료시점을 찾는것에 매우 중요하다.

N개의 수가 주어지므로 DFS 깊이우선탐색에서 깊이가 N인것을 알수 있다.

 

두가지 경우로 하나는 양수 하나는 음수로 하여 재귀함수를 구현하고

깊이가 주어진 배열의길이와 같아지면 종료하여 

배열을 모두 더해  타겟과 같은지 비교하여 같으면 ANSWER를 증가시킨다

 

class Solution {
	
	static int answer = 0;
	
	public void  dfs (int[] numbers, int target, int d) {
		
		if(d == numbers.length) { // 깊이가 배열의 길이와 같다 (모두 탐색 했다)
			int sum = 0 ;
			for(int num : numbers) sum +=num;
			if(sum == target) {
				answer++;
			}
			
			
		}else { // 아직 모두 탐색하지 않았다.
			
			numbers[d] *= 1;  // 하나는 양수로
			dfs(numbers, target, d+1);
			
			numbers[d] *= -1; // 하나는 음수로 
			dfs(numbers,target,d+1);
			
			
		}
		
		
		
	}
	
	
	
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        
        dfs(numbers,target,0);
        
        
        return answer;
    }
}