프로그래머스 - 타겟넘버

타겟넘버

그래프 관련 문제이다.
그래프와 관련된 문제는 나의 많지 않은 코테 경험에서도
(참고로 좋은 경험은 거의 없다 ㅎ)
그래프 관련은 굉장히 자주 출제되었다.

물론 저번에 그래프 문제를 처음 벨로그에서 다룰 때
한 번 유형과 관련해서는 정리를 했다고 생각하기에
여기서는 넘어가겠다.
다만 DFS 얘기는 해야한다.

DFS(Depth First Search)는 깊이 우선 탐색이란 뜻인데,
DFS는 보통 재귀를 통해서 구현한다.
조금 쉽게 설명하면
일단 한 길로 쭈우욱 파보는 것이다.

여기서 이제 쭈우욱 파면서 계속 처리를 하지만
끝까지 갔는데 정답이 아니거나,
중간에 문제의 조건과 이미 부합하지 않을 수도 있다.
이렇게 뭔가 진행이 안되면 되돌아가서 다른 길을 가야 한다.
그러면 이제 백트래킹을 하는 거다.

이렇게 설명하면 이해가 안 될 수도 있는데..

라는 그래프(트리 형태이다)를 보았을 때

BFS의 경우에는 2 -> 7 -> 5 -> 2 -> 6..하고
각 트리의 레벨 순으로 조회를 할 것이고

DFS의 경우에는 2 -> 7 -> 2..하고 (중간에 어떤 조건에 맞지 않는 케이스가 없다면) leaf노드까지 가는 길을 한 길로 방문할 것이다.

나도 사실 DFS와 백트래킹이 너무 어렵다 흑흑

각설하고 문제를 보면, 다행히 순서를 뒤죽박죽 하진 않아도 된다.
순서는 고정이기에, 덧셈 뺄셈에 대해서만 생각하며
DFS를 하면 되는 쉬운 문제이다.

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;
int answer=0;
vector<int> v;
void dfs(vector<int>, int ,int);
int sumOfVector(vector<int> );
int solution(vector<int> numbers, int target) {
    dfs(numbers,0,target);
    return answer;
}
void dfs(vector<int> numbers,int i,int target){
	if(i>=numbers.size()) return ;
	v.push_back(numbers[i]);
	if(v.size()==numbers.size()&&sumOfVector(v)==target) answer++;
	else{
		dfs(numbers,i+1,target);
	}
	v.pop_back();
	v.push_back(numbers[i]*-1);
	if(v.size()==numbers.size()&&sumOfVector(v)==target) answer++;
	else{
		dfs(numbers,i+1,target);
	}
	v.pop_back();
	return;
}
int sumOfVector(vector<int> v){
	int res=0;
	for(auto x : v){
		res+=x;
	}
	return res;
}