[프로그래머스] 타겟 넘버 - JAVA

프로그래머스 - 타겟넘버 문제

 

프로그래머스 - 타겟넘버 입출력 예

 

1. 문제 설명

DFS 재귀호출로 푸는 문제이다. 주어진 number의 요소로 +, - 하면서 depth를 추가하여 마지막 최종 깊이에서 target 값과 같은 가짓수를 리턴하는 문제이다.

 

 

2. 접근방법

처음에 나는 입출력예를 보고 BFS (깊이우선탐색)를 활용하여 문제를 풀려고 했다. 입출력 예를 보면

이 부분이 있는데,

 

아! 전형적인 미로탐색형 탐색문제구나!

 

라고 생각했다. 그래서 맨 윗줄 한줄을 BFS하며 조합의 합이 target값이 되는 조합을 찾으려했다. 하지만, 생각할수록 오류의 연속이었다. target 값을 만들기 위해 주어진 number의 요소를 어떻게 구성할것인가... 여기서 막혀버렸다. (애초에 잘못 접근했으니 막히지..ㅋㅋ)

 

결국 30분이 훌쩍 지나 도움을 얻기로 했다..!

 

 

3. 해결방법

DFS를 활용한 재귀탐색으로 해결하는 문제였다! 루트노드를 0으로 잡고, numbers의 첫번째요소를 +, - 하면서 depth를 1씩 추가하면서 리프노드까지 내려간다. 리프노드의 값이 target값과 같은 가짓수를 count한다. 자세한 설명은 코드 주석으로 설명하겠다.

class Solution {
    // target을 만족하는 가짓수를 count하는 변수
    int count = 0;
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        // DFS 재귀호출
        DFS(numbers, 0, target, 0);
        
        // target을 만족하는 가짓수를 answer에 대입
        answer = count;
        
        // 정답 리턴
        return answer;
    }
    
    /* 
    parameters
        numbers : 대상배열,
        depth : 트리의 깊이,
        target : target값,
        result : 각 노드의 + 또는 -한 과정의 값 (리프노드 시 target값)        
    */
    void DFS(int[] numbers, int depth, int target, int result){
        // 트리의 깊이가 주어진 배열의 length와 같다면 리프노드까지 갔다는 의미
        if(numbers.length == depth){
            // 해당 노드까지의 합이 target과 같다면 정답조건 만족
            if(result == target){
                // 정답 가짓수 + 1
                count++;
            }
            // 종료조건이므로 DFS 종료
            return;
        }
        
        // numbers 요소를 + 하면서 트리를 내려갈때의 과정합
        int plus = result + numbers[depth];
        // numbers 요소흫 - 하면서 트리를 내려갈때의 과정합
        int minus = result - numbers[depth];
        
        // 트리의 다음 깊이로 내려가기 위해 재귀 호출
        DFS(numbers, depth+1, target, plus);
        // 트리의 다음 깊이로 내려가기 위해 재귀 호출
        DFS(numbers, depth+1, target, minus);
    }
}