문제 출처

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

n개의 음이 아닌 정수들의 배열 numbers가 주어질 때, 이를 더하거나 빼서 target이 될 수 있는 경우의 수를 return 하라

접근 방법

dfs를 이용하여 check에 배열의 요소를 더한 check_p와 뺀 check_n을 이용하여 재귀적으로 접근한다.

import java.util.*;


class Solution {
    
    static  int answer;

    public void dfs(int[] numbers, int target, int check, int depth){
        if(check == target && depth == numbers.length){
            answer++;
            return;
        }
        
        if(depth == numbers.length){
            return;
        }
        
        int check_p = check + numbers[depth];
        int check_n = check - numbers[depth];
        
        dfs(numbers, target, check_p, depth + 1);
        dfs(numbers, target, check_n, depth + 1);
        
    }
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        
        dfs(numbers, target, 0, 0);
        return answer;
    }
}

Review
조건 부분과 dfs호출하는 부분을 변경했다.
전체적으로 코드의 흐름은 똑같지만 좀 더 보기 편해보이게 바꿨다.

import java.util.*;

class Solution {

    static int answer;

    public void dfs(int[] numbers, int target, int depth, int check){
        if(depth == numbers.length){
            if(check == target){
                answer++;
                return;
            }
            return;
        }

        check += numbers[depth];
        dfs(numbers, target, depth+1, check);
        check -= 2*numbers[depth];
        dfs(numbers, target, depth+1, check);
    }
    public int solution(int[] numbers, int target) {
        answer = 0;

        dfs(numbers, target, 0, 0);

        return answer;
    }
}

알게된 점

dfs를 이용하는 간단한 문제였다.
기존까지의 dfs는 모든 조합을 만드는 문제가 대다수였기 때문에 for문을 이용하여 각 조합을 바꿔줘야 했지만 이 문제는 배열의 순서를 건들지 않으므로 depth(재귀 횟수)를 index로 사용하여 풀 수 있었다.

문제푼 흔적

Review