[DFS/BFS] 타겟 넘버 - Python / Javascript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

[문제 간단 요약]

1. 숫자 리스트 numbers가 주어짐

2. 숫자를 더하거나 빼서 target이 되는 경우의 수를 구하는 문제

3. 순서대로 연산되며, 모든 경우 탐색 필요

 

[문제 해결 방안]

✅ DFS 방식 (재귀)

• 모든 경우의 수(더하거나 빼거나)를 이진 트리 구조처럼 재귀적으로 탐색
• number를 전부 사용했으면(level == max_level)에 합이 target이면 answer 카운트 증가
• 숫자 배열을 끝까지 탐색한 시점

✅ BFS 방식 (큐)

• 큐를 이용해 sum, index 정보 업데이트
• 각 단계에서 +, - 연산을 큐에 추가  
• 인덱스가 끝까지 도달했을 때, 합이 target이면 카운트 증가

[문제 해결 코드 - python]

def dfs(numbers, val, level, target):
    global max_level, answer
    if level == max_level:
        if val == target:
            answer += 1
        return
    for i in [-1, 1]:
        dfs(numbers, val + i * numbers[level], level + 1, target)

def solution(numbers, target):
    global max_level, answer
    answer = 0
    max_level = len(numbers)
    dfs(numbers, 0, 0, target)
    return answer

 

<함수형으로 개선>

def dfs(numbers, idx, current_sum, target):
    if idx == len(numbers):
        return 1 if current_sum == target else 0
    return (
        dfs(numbers, idx + 1, current_sum + numbers[idx], target) +
        dfs(numbers, idx + 1, current_sum - numbers[idx], target)
    )

def solution(numbers, target):
    return dfs(numbers, 0, 0, target)

 

[문제 해결 코드 - javascript]

 

<기본 큐 방식>

function solution(numbers, target) {
    const queue = [];
    queue.push({ sum: 0, index: 0 });

    let count = 0;

    while (queue.length > 0) {
        const { sum, index } = queue.shift();

        if (index === numbers.length) {
            if (sum === target) {
                count++;
            }
        } else {
            queue.push({ sum: sum + numbers[index], index: index + 1 });
            queue.push({ sum: sum - numbers[index], index: index + 1 });
        }
    }

    return count;
}

 

<개선된 큐 클래스 사용 방식 >

class Q {
    constructor() {
        this.items = [];
        this.head = 0;
    }

    enq(item) {
        this.items.push(item);
    }

    dq() {
        return this.items[this.head++];
    }

    isEmpty() {
        return this.head >= this.items.length;
    }
}

function solution(numbers, target) {
    const q = new Q();
    q.enq({ sum: 0, index: 0 });

    let count = 0;

    while (!q.isEmpty()) {
        const { sum, index } = q.dq();

        if (index === numbers.length) {
            if (sum === target) {
                count++;
            }
        } else {
            q.enq({ sum: sum + numbers[index], index: index + 1 });
            q.enq({ sum: sum - numbers[index], index: index + 1 });
        }
    }

    return count;
}

[코드 개선점]

항목	DFS(재귀)	BFS(큐)
구조	재귀 호출	반복문 + 큐 사용
시간복잡도	O(2ⁿ)	O(2ⁿ)
공간복잡도	O(N) (콜스택)	O(2ⁿ) (큐 저장)
특이사항	간결하지만 스택 제한 우려	명시적 제어, 성능 안정

• JS에서 shift() 사용 시 성능 저하 우려 → 클래스 큐(Q)로 최적화
• Python에서는 global로 answer 추적하지만, 함수형으로 리팩토링도 가능
• BFS 방식은 중간 결과를 저장해 상태를 관리하므로 메모리 사용은 더 많지만 안전