[Java] 타겟 넘버 - Lv2 프로그래머스 깊이 우선 탐색(DFS)

 

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

프로그래머스

 

[알고리즘] 깊이 우선 탐색(DFS)

[알고리즘] 깊이 우선 탐색(DFS)

 

 

프로그래머스 기준 전반적인 2레벨 문제나, 적당한 3레벨문제 정도는 풀 수 있다고 판단되어

미뤄놨던 완전탐색 알고리즘을 연습하기 시작했다.

 

 

풀이

---

문제에서 모든 경우의 수를 파악하라고 했기 때문에 깊이 우선 탐색 알고리즘을 사용하여 해당 문제를 풀었다.

현재 어디까지 탐색했는지 필요했고, 탐색 위치에 따른 합계가 필요해서 각각 idx, sum 파라미터를 사용했다.

class Solution {
	
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }

    
    public void dfs(int[] numbers, int target, int idx, int sum){
        if(idx == numbers.length){
            if(target == sum) answer++;
            return;
        }
        dfs(numbers, target, idx+1, sum+numbers[idx]);
        dfs(numbers, target, idx+1, sum-numbers[idx]);        
    }
}

 

예시 2번인 int[] numbers = {4,1,2,1}, target = 4인 상황을 예로 들면 아래와 같은 그림처럼 될 것이다.

 

numbers[] = {4,1,2,1}일 때

 

 

 

 

 

가장 최후의 노드까지 탐색이 끝나면 리턴시켜 이전 노드로 돌아가며

모든 탐색이 끝나면 종료된다.

if(idx == numbers.length){
    if(target == sum) answer++;
    return;
}

 

BFS를 먼저 다뤄보다가 전혀 감이 안와서 DFS 문제를 풀어보았는데 어느정도 DFS는 다룰 수 있을 것 같다