프로그래머스 - 타겟 넘버(DFS/BFS) / Level 2 / Java

문제 📋

프로그래머스 - 타겟 넘버

DFS 풀이 📝

class Solution {
    private static int answer = 0;

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

    private void dfs(int num, int[] numbers, int index, int target) {
        if (index == numbers.length) {
            if (num == target) {
                answer++;
            }
            return;
        }

        dfs(num + numbers[index], numbers, index + 1, target);
        dfs(num - numbers[index], numbers, index + 1, target);
        return;
    }
}

BFS 풀이 📝

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int start = 0;
        
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        
        for (int num : numbers) {
            int len = queue.size();
            
            for (int i = 0; i < len; i++) {
                int val = queue.remove();
                
                queue.add(val + num);
                queue.add(val - num);
            }
        }
        
        while (!queue.isEmpty()) {
            int val = queue.remove();
            
            if (val == target) {
                answer++;
            }
        }
        return answer;
    }
}

1. 문제 정의
   numbers 배열의 숫자들을 순서를 바꾸지 않고 서로 더하거나 뺐을 때
   target number가 나오는 경우의 수를 구하는 문제이다.

   이 문제의 상태 공간을 트리로서 정의하게 되면
   루트 노드가 0이고 부모 노드 값에서 numbers 배열의 원소를 +, - 한 값을
   자식 노드로 갖는 Binary Tree가 된다.

   따라서 문제는 리프 노드까지 트리를 완전 탐색하고
   리프 노드 중 Target number와 값이 같은 노드의 수를 구하는 것이다.
   

2. 시간 복잡도 계산
   numbers 배열의 길이가 트리의 최대 depth를 의미하며 최대 20이다.
   한 depth마다 +, - 즉, 2개의 자식 노드가 생기기 때문에
   전체 탐색 범위는 2^20, 약 1,000,000개의 노드이다.
   따라서 완전 탐색을 진행해도 충분히 가능하다.

3. 문제 풀이
   완전 탐색을 하면 되기 때문에 DFS, BFS 어떤 것을 사용해도 문제없다.
   따라서 2가지 방식 모두 사용하여 풀어봤다.

   하지만 한 가지 주의할 점이 있는데
   이 문제는 depth마다 자식 노드에 +, - 할 값이 다르다는 것이다.
   (numbers 배열의 원소가 각각 다르기 때문.)

   즉, depth 별로 명확히 나누어서 로직을 처리해야 한다.
   따라서 Stack을 사용한 DFS 풀이에서는 그렇게 하기가 까다롭기 때문에
   재귀를 사용해 풀었으며
   BFS는 depth 처리를 명확하게 하기 위해 한 depth씩 로직 처리를 진행했다.

   추가적으로 두 방법으로 시간 측정을 한 결과 DFS가 약 10배 정도 속도가 빨랐다.
   DFS에서 특별한 가지치기를 통해 탐색 범위를 줄이지 않았기 때문에 탐색 범위는 같았다.
   그래서 그 이유가 궁금했고 추측해 본 결과 2가지 정도의 추측을 할 수 있었다.

   • 재귀 호출의 효율성 : 함수 호출 스택을 사용하여 데이터를 넘겨 주기 때문에 메모리 관리 측면에서 효율적일 수 있다.
     (BFS 풀이에서는 많은 수의 노드들을 큐에 넣어 관리함.)
   • 재귀 호출의 깊이에 따른 최적화 : 컴파일러 차원에서 재귀 호출의 깊이가 일정 수준 이하면 최적화를 수행함. (꼬리 재귀 최적화, 인라인 함수 사용, 레지스터 사용 등)

4. 예외 사항
   기타 특이사항 없음.