[Java] 프로그래머스 : 타겟 넘버(DFS 사용)

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

 

DFS(Depth-first-search) : 깊이 우선 탐색 알고리즘

 각 정점 노드(숫자 지점)를 깊게 탐색하는 방식으로 stack을 쌓으면서 갈 수 있는 최대한 깊이 탐색

 더 이상 탐색할 곳이 없으면 이전 정점으로 돌아가 방문하지 않은 정점으로 향하는 간선을 따라 이동

 

① 우선순위가 높은 곳(작은 수)으로 먼저 이동 

② 더이상 이동할 정점노드가 없을 시 이전 정점으로 돌아간 후 방문하지 않은 정점으로 이동

 

이번 문제를  DFS방식을 이용하는 이유

: 모든 경우의 수를 검사

  모든 노드를 다 훑을때까지 각 노드들을 '더하기/빼기' 하면서 결과값(target)과 같은 값이 나오면 count해줌

 

 

 

문제

 

class Solution {
    int count = 0;

//  numbers : 알고리즘을 실행할 대상 배열
//  depth : 노드의 깊이
//  target : 타겟 숫자
//  sum : 이전 노드까지의 결과 값

    public int solution(int[] numbers, int target){
	// depth, sum = 0 설정    
        dfs(numbers, 0, target, 0);
        int answer = this.count;

        return answer;
    }

    public void dfs(int[] numbers, int depth, int target, int sum) {
        if(depth == numbers.length) {			// 깊이와 마지막 노드까지의 길이가 같을때 
            if(target == sum) {					// target과 노드의 합이 같다면
                this.count++;						// count++한다
            }
        }else {
            dfs(numbers, depth+1, target, sum+numbers[depth]);	// 노드의 값을 더하고 다음 깊이 탐색
            dfs(numbers, depth+1, target, sum-numbers[depth]);	// 노드의 값을 빼고 다음 깊이 탐색
        }
    }
}