[프로그래머스] 깊이 우선 탐색 - 타겟 넘버

numbers의 배열을 가지고 target을 만드는데 필요한 연산은 +-이다.

따라서 연산의 순서는 결과 값에 영양을 끼치지 않는다.

 

가능한 모든 경우를 그래프로 표현하면 이진트리가 만들어진다.

마지막 레벨에서 target과 값이 같으면 +1이고 값이 다르면 다른 것을 탐색하면 된다.

 

나는 깊이 우선 탐색과 이진 트리를 이용하여 문제를 해결해야 겠다는 생각을 하고

무식하게.. 이진트리를 코드로 만들었다..

그랬더니 스택오버플로우 에러... 

아직 재귀 함수 호출하는 코드를 짜는 것이 어렵게 느껴진다.

 

package algorithmStudy;

public class dfsbfs1 {
	static int current=0;
	static int[] arr;
	static boolean[] check;
	static int size;
	static int answer;
	
	static void dfs(int idx, int target) {
		//마지막 레벨 노드인 경우 target과 current 비교
		if(idx>=Math.pow(2, size)-1)
		{
			if(current == target) answer++;
			current -= arr[idx];
			dfs((idx-1)/2,target);		//부모노드로 이동
		}
		//모든 자식 방문한 경우
		if(check[idx*2+1]==true && check[idx*2+2]==true) {
			current -= arr[idx];
			dfs((idx-1)/2,target);		//부모노드로 이동
		}
		current += arr[idx]; 		// 값 추가
		//왼쪽 자식 노드부터 방문
		if(check[idx*2+1]==false) dfs(idx*2+1,target);
		else dfs(idx*2+2,target);
	}
	
	static int solution(int[] numbers, int target) {
	        answer = 0;
	        
	        arr=new int[(int)Math.pow(2, numbers.length+1)-1];
	        check=new boolean[arr.length];
	        size=numbers.length;
	        
	        for(int i=1;i<arr.length;i++) {
	        	check[i]=false; 	// check 초기화
	        	int num=numbers[(int)(Math.log(i+1)/Math.log(2))-1];
	        	if(i%2==0) arr[i]=num*-1;
	        	else arr[i]=num;
	        }
	        
	        dfs(0,target);
	        
	        return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numbers= {1,1,1,1,1};
		int target=3;
		System.out.println(solution(numbers,target));
	}

}

 

이건 나의 코드.. 그냥 생각을 바로 코드로 옮긴 것이다. 

 

 public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = dfs(numbers, 0, 0, target);
        return answer;
    }
    
    private int dfs(int[] numbers, int node, int sum, int target){
        if(node == numbers.length){
            if(sum==target)
                return 1;
            return 0;
        }
        return dfs(numbers, node+1, sum + numbers[node], target) 
        	 + dfs(numbers, node+1, sum - numbers[node], target);
    }

이렇게 간단하게 해결할 수 있다니..

재귀 함수를 이용해서 간단한 코드 작성하는 건 너무 어려운 것 같다..

dfs 안의 return 은 분기를 만들어 주는 것이라고 생각하면 된다.

numbers[node] 값이 양수인 경우와 음수인 경우에 대해 완전 탐색을 한다.