📝 타겟 넘버 (Level 2)

깊이/너비 우선 탐색(DFS/BFS)
타겟 넘버

🔹Python

• 다른 사람의 풀이

def solution(numbers, target):
    leaves = [0] # 모든 계산 결과를 담자
    count = 0
    
    for num in numbers:
        temp = []
        
        # 자손 노드
        for leaf in leaves:
            temp.append(leaf + num) 
            temp.append(leaf - num)
        
        leaves = temp
        # print("leaves:", leaves)

    # 모든 경우의 수 계산 후 target과 같은 지 확인
    for leaf in leaves:
        if leaf == target:
            count += 1
    
    return count

---

🔸Java

• 다른 사람의 풀이

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int solution(int[] numbers, int target) {
        // 현재 노드(숫자의 조합)을 저장하는 리스트
        List<Integer> leaves = new ArrayList<>();
        leaves.add(0);
        int count = 0;
        
        // 모든 숫자에 대해 반복
        for (int num : numbers) {
            List<Integer> temp = new ArrayList<>();
            
            // 자손 노드 생성
            for (int leaf : leaves) {
                temp.add(leaf + num);
                temp.add(leaf - num);
            }
            
            leaves = temp;
        }
        
        // 모든 경우의 수 계산 후 target과 같은지 확인
        for (int leaf : leaves) {
            if (leaf == target) {
                count++;
            }
        }
        
        return count;
    }
}

코드 설명

1. 초기화:
   leaves 리스트는 현재 노드(숫자의 조합)를 저장합니다. 시작 값으로 0을 리스트에 추가합니다.
   count 변수는 목표 값을 찾은 경우의 수를 세기 위해 사용됩니다.

2. 숫자 순회:
   입력된 numbers 배열의 각 숫자에 대해 반복합니다. 각 숫자에 대해, 현재 leaves 리스트에 있는 각 값에서 해당 숫자를 더하거나 빼는 두 가지 새로운 값을 만듭니다. 이 두 값은 자손 노드로 간주됩니다. temp 리스트에 이 두 가지 경우를 모두 추가합니다.

3. leaves 리스트 업데이트:
   각 숫자에 대해 leaves 리스트를 업데이트하여 다음 숫자를 처리할 때 사용할 수 있도록 합니다. 즉, 이전에 생성된 모든 자손 노드들이 다음 반복에서 새로운 leaves가 됩니다.

4. 목표 값 확인:
   모든 숫자를 처리한 후, 최종적으로 leaves 리스트에 남아 있는 값들이 목표 값 target과 일치하는지 확인합니다. 일치하는 값이 있으면 count를 증가시킵니다.

5. 결과 반환:
   count를 반환하여, 목표 값에 도달한 모든 경우의 수를 반환합니다.

BFS (너비 우선 탐색) 이유:

• BFS 특성: BFS는 모든 가능한 경우를 한 단계씩 확장하면서 탐색합니다. 이 코드에서는 각 숫자를 더하거나 빼는 두 가지 선택지를 모든 경우에 대해 동시에 고려하며 진행합니다. 즉, 각 단계에서 가능한 모든 조합을 확장한 후, 다음 숫자로 넘어가면서 이를 반복합니다.

• DFS와의 차이점: DFS는 하나의 경로를 끝까지 탐색한 후에 다른 경로로 이동하지만, 이 코드에서는 모든 가능한 경로를 동시에 탐색하며 진행하기 때문에 BFS에 해당합니다.