프로그래머스 C++ 타겟 넘버 (DFS)

DFS는 너무 오랜만이라... 기억하기 위해 쓴다.

[프로그래머스] 타겟 넘버(BFS,DFS) / C++ (velog.io)

[프로그래머스] 타겟 넘버(BFS,DFS) / C++

(참조한 블로그)

 

우선, 깊이우선탐색은 기본적으로 재귀의 형태를 쓴다.

한 DFS함수를 main에다가 구현하는데 맨 처음 index값은 0으로 설정하고, 그 외의 매개변수로는 배열과 다른 필요한 값들을 항시 들고 다니며 값을 변환시켜준다.

그 안에서 별도로 값을 변환시켜줘야 하는 것은 전역변수의 형태를 보통 취한다.

재귀의 형태를 쓴다는 것은 "내 속에 내가 너무도 많아.." 즉, 함수 안의 함수 안의 함수... 형태를 띄는데 이를 즉시 탈출하는 방법은 Return입니다.

보통 재귀함수는 함수 안의 함수 . 그게 끝이지만 이 DFS문에서는 함수 안에 두개의 함수를 품고 있습니다.

보통의 재귀함수의 형태

return문 한번이면 즉시 종료됩니다.

DFS에서 쓰는 재귀함수.

위와 같은 경우에는 return이 16번 실행됩니다.

이 문제는 백트래킹 문제는 아니다.

백트래킹은 DFS를 이용하긴 하지만, visited와 같은 배열을 이용해서 한 블럭 이전으로 돌아가서 실행하기 때문이다.

#include <string>
#include <vector>

using namespace std;
int answer = 0;//전역변수로 선언
int num = 0;
void DFS(vector<int> numbers, int target, int sum, int index){//이 안에서의 변수 크기 변화는 매개변수로 시켜줌
    if(index == numbers.size())//가장 먼저 지금이 끝까지 내려갔는지 확인.재귀 각 실행시마다의 종료 조건만을 설정(index가 끝까지 갔을 때)//index가 더이상 numbers를 참조할 수 없어질 때.
    {
        if(sum == target)
            answer++;
        return;
    }
    DFS(numbers, target, sum + numbers[index] , index + 1);//sum += numbers[index], index += 1
    DFS(numbers, target, sum - numbers[index], index + 1);//sum -= numbers[index], index += 1
}

int solution(vector<int> numbers, int target) {
    cout << num << endl;
    DFS(numbers, target, 0, 0);//main에서 함수 실행 시에는 sum, index가 처음(0)에서 시작하도록 해야함.
    return answer;
}

이러한 형태를 기억해두면 좋을 것 같다.