10. C++ 타겟넘버, DFS, 깊이우선탐색

* 개인 공부를 위하여 간단하게 정리한 것입니다. 

* 틀린 부분 지적은 언제나 환영입니다.

 

오늘은 프로그래머스 코딩 예제인 '타겟넘버'를 DFS를 이용하여 푸는 방법에 대하여 알아보겠습니다.

 

 

numbers 벡터의 인덱스를 하나씩 진행해 가면서 '+' , '-'의 모든 결과를 확인해 보아야 합니다.

DFS로 푼 이유는 노드의 자식노드를 호출하고 연산하는 방법에 착안하여 진행하였기 때문입니다.

DFS는 Stack이나 재귀함수(Reculsive Function)를 이용하여 구현 가능하며, 본문의 코드는 재귀함수로 구성하였습니다.

 

 

* 다음 코드는 프로그래머스를 통과한 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

int ans = 0;
int t;
int k = 0;
void dfs(vector<int>& numbers, int n, int sum)
{
	 
	if (n == numbers.size()) {
		if (sum == t)
		{
			++ans;
			return;
		}
		else
		return;
	}
	
		dfs(numbers, n + 1, sum + numbers[n]);
		dfs(numbers, n + 1, sum - numbers[n]);
	
}


int solution(vector<int> numbers, int target) {

	t = target;
	dfs(numbers, 0, 0); // array, n-th, sum
	return ans;
}

 

* 다음 코드는 Visual Studio 환경에서 해당 문제를 테스트 하기 위하여 구현한 전체 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

int ans = 0;
int t;
int k = 0;
void dfs(vector<int>& numbers, int n, int sum)
{
	 
	if (n == numbers.size()) {
		if (sum == t)
		{
			++ans;
			return;
		}
		else
		return;
	}
	
		dfs(numbers, n + 1, sum + numbers[n]);
		dfs(numbers, n + 1, sum - numbers[n]);
	
}


int solution(vector<int> numbers, int target) {

	t = target;
	dfs(numbers, 0, 0); // array, n-th, sum
	return ans;
}

int main() {
	vector<int> numbers = {1, 1, 1, 1, 1};
	int target = 3;

	int ret = solution(numbers, target);
	cout << ret << endl;
	
	return 0;
}