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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

---

고민1. 깊이/너비 우선 탐색(DFS/BFS)

개념을 알고 있는데 이렇게 문제로 만나니까 갑자기 머리가 안돌아갔다...
DFS는 재귀로 구현하면 되겠다! 하고 바로 생각이 났는데
BFS는 어떤식으로 짜야하는지 도무지 생각이 안나서(갑자기 개념까지 헷갈리기 시작..)
한참을 고민하다 결국 구글링을 약간 했다ㅠ

일단 개념을 되짚어보면...

1. 깊이 우선 탐색

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

2. 너비 우선 탐색

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

문제로 돌아와서, '타겟 넘버를 만드는 방법의 수'를 구할 때

• DFS 방식은 [+1+1+1+1], [+1+1+1-1], [+1+1-1+1], ... 과 같이 순차적으로 식을 만들고
  타켓과 일치하면 카운트를 누적시키는 형식으로 구현될 것이고

• BFS 방식은 수평으로 값을 더하거나 뺀 값을 저장하여 마지막 노드에 도달하면 총 16가지의 결과값(전체 경우의수=2^4)이 구해지고 이 중에서 타켓과 일치 하는 값의 개수를 구하는 형식으로 구현될 것이다

고민2. 깊이 우선 탐색(DFS)으로 구현

마지막 노드까지(탈출 조건) sum에 더하거나 빼는 재귀 함수를 호출하고,
마지막 노드에 도착했을 때 sum이 target과 일치하면 카운트를 추가한다.

class Solution {
    int answer = 0;
    
    public void dfs(int[] numbers,int depth, int target, int sum){
        if(depth==numbers.length){  // 마지막 노드 재귀 탈출
            if(target == sum) answer++;
            return;
        }
        dfs(numbers, depth+1,target, sum+numbers[depth]);
        dfs(numbers, depth+1,target, sum-numbers[depth]);
    }
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target,0);
        return answer;
    }
}

고민3. 너비 우선 탐색(BFS)으로 구현

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    int answer = 0;

    public void bfs(int[] numbers, int target){
        ArrayList<Integer> sumList=new ArrayList<>() ;
        sumList.add(0);
        
        for(int num:numbers){
            ArrayList<Integer> temp=new ArrayList<>() ;
            for(int sum:sumList){
                temp.add(sum+num);
                temp.add(sum-num);
            }
            sumList=(ArrayList<Integer>) temp.clone();
        }
        answer = Collections.frequency(sumList, target);
    }

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

성능 비교

1. 깊이 우선 탐색
   

2. 너비 우선 탐색
   

속도, 메모리 모두 깊이 우선 탐색이 좋아 보인다.

---

최종코드

GitHub Java-algorithm-practice/프로그래머스/lv2/43165. 타겟 넘버/

class Solution {
    int answer = 0;
    
    public void dfs(int[] numbers,int depth, int target, int sum){
        if(depth==numbers.length){  // 마지막 노드 재귀 탈출
            if(target == sum) answer++;
            return;
        }
        dfs(numbers, depth+1,target, sum+numbers[depth]);
        dfs(numbers, depth+1,target, sum-numbers[depth]);
    }
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target,0);
        return answer;
    }
}