[프로그래머스] 타겟 넘버(Java)

타겟 넘버

배경 지식

저는 스스로 해결 못했습니다… ㅠㅠ
다른 사람들의 풀이를 참고한 결과 DFS 또는 BFS를 사용하여 해결할 수 있었습니다!!

DFS, BFS는 완전 탐색 알고리즘으로
완전 탐색 이란?
가능한 모든 경우의 수를 다 확인해서 정답을 찾는 방법입니다.

아래 영상을 보면 DFS, BFS에 대하여 이해하기 쉬울 것 입니다.^^
DFS BFS 깊이 너비 우선탐색 알고리즘 5분만에 이해하기

DFS

깊이 우선 탐색을 의미 합니다.
쉽게 이야기 하면 원하는 결과를 찾을 때 까지 한놈만 죽어라 탐색 하는 알고리즘 입니다.

알고리즘 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667 -Java)

BFS

너비 우선 탐색을 의미합니다.
쉽게 이야기하면 원하는 결과를 찾을 때 까지 여러 곳을 한 번에 탐색하는 알고리즘 입니다.

알고리즘 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java)

그러면 DFS, BFS 어떤게 이득이야?

우리가 원하는 값이 어느 지점에 위치 하는지 알 수 없기 때문에 어떤것을 사용하는것이 더 좋은지 알기 어렵습니다.😭

DFS는 운이 좋으면 첫 번째 조합에서 최적의 답을 도출할 수 있습니다.
이러한 특징은 수행 시간 관점에서 BFS보다 큰 이득을 볼 수 있습니다.
최악의 경우에는 모든 조합을 다 만들어보면서 수행시간에서 큰 손해를 볼 수 있습니다.. ㅠ0ㅠ

BFS는 모든 경우의 수를 하나씩 조합해보기 때문에 초반에는 느려보일 수 있지만, 하나의 정답을 찾고나면 나머지 경우의 수는 정답에서 제외 되는 경우가 많습니다.
쉽게 이야기 하면 일정한 시간 복잡도를 갖고 있다고 이야기할 수 있습니다.

해결 방법

numbers에 있는 숫자의 모든 +, -조합을 확인하여 해결하는 방식의 문제 입니다.
모든 조합을 확인하는 방법에는 DFS, BFS 2가지 방법이 있습니다.

• DFS 또는 BFS 사용
• 마지막 노드까지 탐색(더하기 연산 or 빼기 연산)했을 때 타겟 값(target)이 정답(result)과 같으면 카운트(count) 증가

풀이

DFS

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

    private static int dfs(int[] numbers, int target, int depth, int result) {
        int count = 0;
        // 깊이 탐색을 마쳤을 때
        if(numbers.length == depth) {
            // 결과가 타겟값과 일치하면
            if(result == target) {
                count++;
            }
        } else {
            // 깊이를 1 증가, result에 numbers의 depth에 해당하는 값을 더함
            count += dfs(numbers, target, depth + 1, result + numbers[depth]);
            // 깊이를 1 증가, result에 numbers의 depth에 해당하는 값을 뺌
            count += dfs(numbers, target, depth + 1, result - numbers[depth]);
        }

        return count;
    }
}

BFS

static class Solution {
    public int solution(int[] numbers, int target) {
        return bfs(numbers, target);
    }

   // 너비 우선 탐색
   private int bfs(int[] numbers, int target) {
        Queue<Node> queue = new ArrayDeque<>();
        // 초기 탐색 값 설정
        queue.add(new Node(0, numbers[0]));
        queue.add(new Node(0, numbers[0] * -1));

        int count = 0;
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            // 너비 탐색을 마치면
            if(poll.getNode() == numbers.length - 1) {
                // 타겟값 이면
                if (poll.getResult() == target) {
                    // 카운트 증가!
                    count++;
                }
            }

            // 인덱스 증가
            int newNode = poll.getNode() + 1;
            if(newNode < numbers.length) {
                // 더하기 연산
                queue.add(new Node(newNode, poll.getResult() + numbers[newNode]));
                // 빼기 연산
                queue.add(new Node(newNode, poll.getResult() - numbers[newNode]));
            }
        }

        return count;
    }

   class Node {
        private int node;
        private int result;

        public Node(int node, int result) {
            this.node = node;
            this.result = result;
        }

        public int getNode() {
            return node;
        }

        public int getResult() {
            return result;
        }
    }
}