[고득점Kit][DFS] 타겟 넘버 ⭐⭐

[DFS] 타겟 넘버

난이도 ⭐⭐

문제

풀이

이 문제는 풀지 못 했다. 더군다나 문제도 잘 못 이해했다. 순열처럼 numbers 원소들의 자리들도 바꿔야 하는건 줄 알았는데 생각해보니 그렇게는 안해도 됐었다.. 그냥 -, + 부호를 어디에 붙일지만 고려하면 될 뿐이었다. 아무튼간에.. 풀이를 구글링해보니 내가 백준에서 풀었던 문제들과 유형이 똑같다는걸 깨달았다. 이런게 DFS구나 !!! DFS 문제 더 많이 풀어봐야 겠다고 느꼈다. 재귀는 언제나 좀 낯설다. 개념이.. ㅠㅠ 아무튼 ~~ 할 수 ItDa 💛💛

#include <string>
#include <vector>

using namespace std;

void DFS(vector<int>& numbers, int& answer, int target, int count, int sum)
{
    if (count == numbers.size() - 1)
    {
        if (sum + numbers[count] == target) answer++;
        if (sum - numbers[count] == target) answer++;
        return;
    }
    
    DFS(numbers, answer, target, count + 1, sum + numbers[count]);
    DFS(numbers, answer, target, count + 1, sum - numbers[count]);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    DFS(numbers, answer, target, 0, 0);
    
    return answer;
}

numbers 원소들의 순서는 그대로 유지한 체로, 각각 재귀 과정에서 두번의 DFS 재귀를 진행한다. 한번은 + 하는걸로, 한번은 - 하는걸로.

한 단계씩 재귀를 할 때마다 종료 조건에 수렴하도록 인수를 넘겨야 한다.

target이 2인 [1, 3, 5, 7, 10] 을 예로 들자면

• DFS(0, 0)
  • 1️⃣ DFS(1, 0 + 1)
    • 1️⃣ DFS(2, 0 + 1 + 3)
      • 1️⃣ DFS(3, 0 + 1 + 3 + 5)
        • 1️⃣ DFS(4, 0 + 1 + 3 + 5 + 7)
          • 0 + 1 + 3 + 5 + 7 + 10 은 target이 아니므로 answer를 증가시키지 않는다.
          • 0 + 1 + 3 + 5 + 7 - 10 은 target이 아니므로 answer를 증가시키지 않는다.
          • return 종료
        • 2️⃣ DFS(4, 0 + 1 + 3 + 5 - 7)
          • 0 + 1 + 3 + 5 - 7 + 10 은 target이 아니므로 answer를 증가시키지 않는다.
          • 0 + 1 + 3 + 5 - 7 - 10 은 target이 아니므로 answer를 증가시키지 않는다.
          • return 종료
      • 2️⃣ DFS(3, 0 + 1 + 3 - 5)
        • 1️⃣ DFS(4, 0 + 1 + 3 - 5 + 7)
          • 0 + 1 + 3 - 5 + 7 + 10 은 target이 아니므로 answer를 증가시키지 않는다.
          • 0 + 1 + 3 - 5 + 7 - 10 은 target이 아니므로 answer를 증가시키지 않는다.
          • return 종료
        • 2️⃣ DFS(4, 0 + 1 + 3 - 5 - 7)
          • ✨ 0 + 1 + 3 - 5 - 7 + 10 은 target이 맞으므로 answer를 증가시킨다.
          • 0 + 1 + 3 - 5 - 7 - 10 은 target이 아니므로 answer를 증가시키지 않는다.
          • return 종료

…

대충 이런식이다!

void DFS(vector<int>& numbers, int& answer, int target, int count, int sum)
{
    if (count == numbers.size() - 1)
    {
        if (sum + numbers[count] == target) answer++;
        if (sum - numbers[count] == target) answer++;
        return;
    }
    
    DFS(numbers, answer, target, count + 1, sum + numbers[count]);
    DFS(numbers, answer, target, count + 1, sum - numbers[count]);
}

DFS 그래프의 모든 노드를 순회하는 방법 중 하나로 일단 깊숙이 계속해서 끝까지 들어간 후 되돌아 와 또 내려갈 곳을 찾으면 또 깊숙이 내려간다. ㅇㅇ count는 numbers의 인덱스로도 활용되며 재귀 단계의 깊이를 뜻하기도 한다. 끝까지 도달했다면 종료해야 한다. if (count == numbers.size() - 1)

1. 현재 단계(인덱스)가 +인 버전에서의 다음 단계 재귀 진행. 다음 단계에서도 똑같이 +, - 두 단계 버전으로 각각 재귀를 하게 된다.
2. 현재 단계(인덱스)가 -인 버전에서의 다음 단계 재귀 진행. 다음 단계에서도 똑같이 +, - 두 단계 버전으로 각각 재귀를 하게 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기