프로그래머스lv2-타겟넘버

이전부터 dfs/bfs에 대한 문제가 나오면 굉장히 당황하고 문제 해결방법을 몰라서 dfs/bfs에 대해서 두려워하고 어떻게 구현할지 고민많이 햇다.

하지만 두려워만해서는 더나은사람이 못되는법!

dfs에 대해 탐구하고 용기를 가지고  풀게된 첫번째 문제이다.

dfs는 재귀함수 혹은 큐를 통해 해결할수잇다는 문서를 보고 힌트를 얻어서 30분 머리싸매고 풀었다.

 

1. dfs는 모든 경우의수를 확인해야한다. 타겟넘버에서는 배열이 각 음수, 양수인지 확인하여 최종 배열의 합계를 더하면된다.

2. 그러면 각 배열 i번째를 음수/양수 처리하고 i+1번째에서 함수를 다시 호출하자
※이때 i는 0부터 시작 배열은 0부터 시작이니까

3. i가 배열의 끝까지 갓을때 모든합계를 더하여 target넘버랑 일치하면 전역변수에 값을1추가하고 그모든 경우의 수를 정답으로 return해주자

아래는 내가 작성한 풀코드이다.

package lv2;

import java.util.Iterator;

public class target_num {
	
	static int result_num=0;
	
	public static void main(String[] args) {
		
//		int number[] = {1, 1, 1, 1, 1};
//		int target = 3;
		
		int number[] = {4, 1, 2, 1};
		int target = 4;
		
		
		solution(number,target);
		
		System.out.println("answer is ="+result_num);
	}
	
    public static int solution(int[] numbers, int target) {
        int answer = 0;
               
        
        dfs(0,numbers,target);
        
        return answer;
    }

	private static void dfs(int i, int[] numbers, int target) {
		// TODO Auto-generated method stub
		
		if(i==numbers.length) {
			int result=0;
			for(int sum : numbers)
				result+=sum;
			
			if(result==target) {
				//showarr(numbers);				
				result_num++;
			}
			
		}else {
			//i번째 행을 양수로 재귀호출
			dfs(i+1,numbers,target);			
			
			//i번째 행을 음수로 재귀호출
			numbers[i]=-numbers[i];
			dfs(i+1,numbers,target);
		}
		
		
	}

	private static void showarr(int[] numbers) {
		System.out.print("arr is\t");
		for(int re : numbers) {
			System.out.print(re+", " );
		}
		System.out.println("\n\n");
			
		
	}

}