[DFS/BFS] 타겟 넘버

Wintering·2022년 8월 23일
0

Algorithm

목록 보기
13/16

1h30m

  1. 깊이 우선 탐색을 사용하여 numbers 배열의 전체 숫자 탐색
    • 재귀함수 사용, 배열을 돌면서 배열의 전체값들이 각각 +,-인 경우를 탐색하며 총합을 구해준다.
    • 총합이 target과 같은 값일 때만 answer에 카운트를 올려준다.
/**
 * 깊이/너비 우선탐색 : 타겟넘버
 */
public class Solution {
    int answer = 0;

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

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


0개의 댓글