[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

문제

풀이

#include <string>
#include <vector>

using namespace std;
vector<int> datas;
int answer;
int tarN;
void dfs(int n, int before);

int solution(vector<int> numbers, int target) {
    answer = 0;
    datas = numbers;
    tarN = target;
    dfs(0, 0);
    
    return answer;
}

void dfs(int n, int before){
    if(n == datas.size()){
        if(before == tarN) answer++;
        return;
    }
    
    dfs(n+1, before + datas[n]);
    dfs(n+1, before - datas[n]);
    return;
}

dfs를 사용하여 모든 경우의 수를 구했다.

---

다른 사람 풀이 1

#include <string>
#include <vector>

using namespace std;

int total;

void DFS(vector<int> &numbers, int &target,int sum,int n) {
    if(n >= numbers.size()){
        if(sum == target) total++;
        return;
    }

    DFS(numbers, target, sum + numbers[n], n+1);
    DFS(numbers, target, sum - numbers[n], n+1);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    DFS(numbers, target, numbers[0] , 1);
    DFS(numbers, target, -numbers[0], 1);

    answer = total;

    return answer;
}

시작을 더했을 때, 뺐을 때로 정해놓고 각각 dfs를 실행한 듯하다!

내 코드는 전역 변수가 많지만, 이 코드는 참조자를 이용했기 때문에 코드가 더 깔끔하다.

 

포인터와 레퍼런스는 비슷한 기능을 하고 있는 것처럼 느껴져 자주 헷갈리고 또한 중요하기 때문에 따로 정리를 해 두었다.

밑의 링크를 확인!

https://strong-2-min.tistory.com/93

참조자(레퍼런스)와 포인터

 

 

다른 사람 풀이 2

#include <string>
#include <vector>


using namespace std;


int answer = 0;
int solution(vector<int> numbers, int target) {


    if (numbers.size()==0 && target==0) {
        return 1;
    }
    else if (numbers.size() == 0) {
        return 0;
    }

    int temp = numbers[0];
    numbers.erase(numbers.begin());

    return solution(numbers, target + temp) + solution(numbers, target - temp);

}

재귀 함수를 사용한 풀이이다.

 

코드는 다 다르지만 모두 비슷한 방법으로 풀었다!

 

 

---

https://copycode.tistory.com/82

C++ 강의 7장 - 참조자(Reference) -

https://easycoding91.tistory.com/4 

[C++ 강좌] 참조자(Reference)의 개념과 함수 활용