💻 오늘의 문제

• 알고리즘: DFS/BFS
• 문제 링크: 타겟 넘버

풀이 과정

import java.util.*;

class Solution {

    public int solution(int[] numbers, int target) {

        // return dfs(0, 0, target, numbers);

        return bfs(numbers, target);
    }

    private int dfs(int idx, int sum, int target, int[] numbers) {

        if(idx == numbers.length) {
            return sum == target ? 1 : 0;
        }

        return dfs(idx + 1, sum + numbers[idx], target, numbers)
             + dfs(idx + 1, sum - numbers[idx], target, numbers);
    }

    private int bfs(int[] numbers, int target) {

        int answer = 0;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0));

        while(!queue.isEmpty()) {

            Node now = queue.poll();

            if(now.idx == numbers.length) {

                if(now.sum == target) {
                    answer++;
                }

                continue;
            }

            queue.offer(
                new Node(
                    now.idx + 1,
                    now.sum + numbers[now.idx]
                )
            );

            queue.offer(
                new Node(
                    now.idx + 1,
                    now.sum - numbers[now.idx]
                )
            );
        }

        return answer;
    }

    static class Node {
        int idx;
        int sum;

        Node(int idx, int sum) {
            this.idx = idx;
            this.sum = sum;
        }
    }
}

• 문제 핵심:
• DFS는 재귀,깊게 끝까지 파고 넘어가는 걸 이해하기.
• BFS는 Queue로, 순차적으로 넓게 진행 된다는 걸 이해하기.

📌 느낀 점

DFS/BFS 패턴의 감을 익힌다면 쉽게 풀릴것이라 생각한다. 그래서 패턴을 익히기 이전엔 '재귀'와 '큐'를 이해하고 푸는 것이 수월할 것이다.