11. 타겟넘버, BFS, 너비우선탐색

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

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

 

지난번 타겟넘버 문제는 DFS를 이용하여 해결하였습니다. 오늘은 BFS를 이용하여 '타겟넘버'를 해결하여 보겠습니다.

 

이 문제를 BFS로 접근하면 다음과 같이 생각할 수 있습니다.

 

 

즉, 첫 번째 numbers의 노드를 기준으로 다음번 노드의 덧셈과 뺄셈한 값을 구하는 방법을 진행합니다. 이렇게 되면 리프노드에는 numbers 노드의 수만큼 덧셈 혹은 뺄셈한 결과가 저장됩니다.

이 리프노드 중에서 target 값과 일치하는 노드의 개수를 구하면 됩니다.

 

코드는 다음과 같습니다.

 

int solution2(vector<int> numbers, int target) {
	int ans2 = 0;
	vector<int> arr_bfs;
	arr_bfs.push_back(0);
	
	vector<int> tmp;
	for (int i = 0; i < numbers.size(); i++) {
		tmp.clear();
		for (int j = 0; j < arr_bfs.size(); j++) {
			tmp.push_back(arr_bfs[j] + numbers[i]);
			tmp.push_back(arr_bfs[j] - numbers[i]);
		}
		arr_bfs = tmp;
	}

	for (int i = 0; i < arr_bfs.size(); i++) {
		if (arr_bfs[i] == target)
			++ans2;
	}

	return ans2;
}

테스트를 포함한 전체 코드는 다음과 같습니다.

(DFS, BFS 풀이 모두 포함 / DFS: Solution , BFS: Solution2)

 

#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 solution2(vector<int> numbers, int target) { //BFS
	int ans2 = 0;
	vector<int> arr_bfs;
	arr_bfs.push_back(0);
	
	vector<int> tmp;
	for (int i = 0; i < numbers.size(); i++) {
		tmp.clear();
		for (int j = 0; j < arr_bfs.size(); j++) {
			tmp.push_back(arr_bfs[j] + numbers[i]);
			tmp.push_back(arr_bfs[j] - numbers[i]);
		}
		arr_bfs = tmp;
	}

	for (int i = 0; i < arr_bfs.size(); i++) {
		if (arr_bfs[i] == target)
			++ans2;
	}

	return ans2;
}

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

	int ret = solution(numbers, target); //DFS
	cout << ret << endl;

	int ret2 = solution2(numbers, target); //BFS
	cout << ret2 << endl;
	
	return 0;
}