[알고리즘] 프로그래머스 - 타겟 넘버

programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

import java.util.*;

class Solution {
    
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    public int dfs(int[] numbers, int target, int depth, int value) {
        if (depth == numbers.length) {
            if (value == target) {
                return 1;
            }
            return 0;
        }
        int plus = dfs(numbers, target, depth + 1, value + numbers[depth]);
        int minus = dfs(numbers, target, depth + 1, value - numbers[depth]);
        
        return plus + minus;
    }
    
}

dfs를 통해 문제를 해결하였다.

 

재귀함수의 depth가 numbers.length가 된다면 sum이 target과 동일한지 검색한다.

 

동일하다면 1을 반환하여 카운트를 하나 높여준다.

 

위와 같이 두개의 재귀함수를 돌리게 되면 아래와 같은 탐색과정이 나온다.

 

 

첫번째 재귀함수 빨간 부분의 트리를 만들고,

 

그 이후로 return라인의 오른쪽 재귀함수가 호출되어 현재 인덱스값을 이전 인덱스값에서 빼주는 과정을 수행한다.

 

 

# BFS 풀이 추가

import java.util.*;

class Solution {
    
    public int solution(int[] numbers, int target) {
        // return dfs(numbers, target, 0, 0);
        return bfs(numbers, target);
    }
    
    public int bfs(int[] numbers, int target) {
        int plus = numbers[0];
        int minus = numbers[0] * -1;
        int count = 0;
        
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(plus, 0));
        queue.add(new Location(minus, 0));

        while (!queue.isEmpty()) {
            Location current = queue.poll();
            
            if (current.x == target && current.y == numbers.length - 1) {
                count++;
            }
            
            if (current.y < numbers.length - 1) {
                Location nextPlus = new Location(current.x + numbers[current.y + 1], current.y + 1);
                Location nextMinus = new Location(current.x - numbers[current.y + 1], current.y + 1);
                
                queue.add(nextPlus);
                queue.add(nextMinus);
            }
        }
        return count;
    }
    
    class Location {
        int x;
        int y;
        
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

BFS 풀이는 DFS보다 다소 복잡하다.

 

처음 시작할 때, 큐 안에 양수로 시작하는 숫자와 음수로 시작하는 숫자를 모두 넣어 풀이를 진행한다.

 

입력으로 주어진 모든 숫자를 다 쓸 때까지, 다음 숫자를 더한값과 뺀값을 모두 큐에 집어넣는다.

 

그렇게 하고 큐에서 빠지는 값들이 target과 일치하며, 그 값은 모든 숫자를 다 써서 나왔다는 것이 증명되면 

 

count를 1씩 더해준 후 마무리한다.