반응형
* 개인 공부를 위하여 간단하게 정리한 것입니다.
* 틀린 부분 지적은 언제나 환영입니다.
지난번 타겟넘버 문제는 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;
}
반응형
'공부 > C++' 카테고리의 다른 글
리눅스 Permission denied / cannot execute binary file (0) | 2022.07.15 |
---|---|
#pragma once, C++의 header (0) | 2022.07.05 |
13. C++ Reference, 참조 (0) | 2022.01.27 |
C++ 변수 선언 (uniform initialization), preventing narrow (0) | 2022.01.04 |
10. C++ 타겟넘버, DFS, 깊이우선탐색 (0) | 2021.09.08 |
9. C++ 미로찾기(Queue, Maze) (0) | 2021.08.19 |
8. C++ 동적프로그래밍, 재귀, Top Down, Bottom Up, 피보나치 (0) | 2021.08.19 |
7. C++ 오름차순 정렬 (vector, sort, ascending, descending) (0) | 2021.08.19 |