[Algorithm/Programmers] 자바 - 타겟 넘버

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
타겟 넘버	Programmers	Level 2	DFS/BFS	풀이	문제

풀이

n개의 음이아닌 정수를 적절히 더하거나 빼서 타겟 넘버를 만들면 됩니다.

간단히 dfs/bfs로 완전 탐색하면 되는 문제입니다.
dfs로 하는 게 좋아보이지만, input이 작으므로 bfs로도 풀어보겠습니다.

Case 1: DFS

class Solution {
    private int count = 0;
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, target, 0, 0);
        
        return count;
    }
    
    private void dfs(int[] numbers, int target, int depth, int sum) {

        if (depth == numbers.length) {
            if (sum == target)
                count += 1;
            return;
        }

        dfs(numbers, target, depth + 1, sum + numbers[depth]);
        dfs(numbers, target, depth + 1, sum - numbers[depth]);

    }

Case 2: BFS

import java.util.*;

class Solution {
    
    public int solution(int[] numbers, int target) {
        
        int answer = bfs(numbers, target);

        return answer;
    }
    
    private int bfs(int[] numbers, int target) {
        int count = 0;
        Queue<Number> q = new LinkedList<>();
        q.offer(new Number(numbers[0], 0));
        q.offer(new Number(-numbers[0], 0));
        
        while (!q.isEmpty()) {
            Number p = q.poll();
            if (p.index == numbers.length - 1) {
                if (p.sum == target)
                    count += 1;
                continue;
            }
            
            q.add(new Number(p.sum + numbers[p.index + 1], p.index + 1));
            q.add(new Number(p.sum - numbers[p.index + 1], p.index + 1));
        }
        return count;
    }

    private class Number {
        int sum;
        int index;

        Number(int sum, int index) {
            this.sum = sum;
            this.index = index;
        }
    }
}