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

 알고리즘 

 

그래프에서 모든 노드를 방문해야 할 때 DFS 또는 BFS 를 사용한다.

DFS(깊이우선탐색 - Depth First Search)는 그래프에서 아래로 내려갈 수 있을 때까지 갔다가 막히면 되돌아와서 다시 내려가는 탐색 방법이고

BFS(너비우선탐색 - Breadth First Search)는 그래프에서 한 노드에서 인접한 노드를 다 살핀 후 인접한 노드의 인접한 노드를 같은 방식으로 살피는 탐색 방법이다. 

 

 문제 

 

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

 

 문제이해 

 

  numbers = [ x, y, z ] 라고 하자 (x, y, z는 정수). 첫 번째 요소부터 시작하면 +x, -x로 시작할 수 있다. 다음은 +x와 -x에 각각 +y, -y가 되므로 +x+y, +x-y, -x+y, -x-y 4가지 경우가 나온다. 마지막으로 앞의 4가지 경우에 +z, -z를 하면, +x+y+z, +x+y-z.+x+y+z,+x+y-z,-x+y+z,-x+y-z,-x-y+z,-x-y-z 이렇게 8가지 경우가 나온다.

  따라서 numbers의 첫 번째 요소부터 마지막 요소까지 +와 -를 반복하여 모든 케이스를 구해주면 된다.

 

 소스코드 

 

/* 타겟 넘버 */
#include <string>
#include <vector>

using namespace std;
int answer = 0;

void targetNumber(vector<int> numbers, int target, int sum, int count) {
    if(count == numbers.size()) {
        if(sum == target) answer++;
        return;
    }
    targetNumber(numbers, target, sum+numbers[count], count+1);
    targetNumber(numbers, target, sum-numbers[count], count+1);
}
int solution(vector<int> numbers, int target) {
    targetNumber(numbers, target, 0, 0);
    return answer;
}

 

- count 변수는 dfs의 depth를 의미하기도 하지만 numbers의 인덱스로 이용되기도 한다.

- targetNumber의 count+1을 count++로 하면 에러가 난다. 이유를 고심해 봤는데, count++은 count값 자체를 바꾸는 것인데 같은 라인(sum+numbers[count])에서 count 변수를 사용하기 때문인 것 같다.

- 모든 경우의 수를 표를 그려보면 더 쉽게 이해할 수 있다.