[프로그래머스/C++] 타켓넘버 - DFS (깊이우선탐색)
- 타겟 넘버
문제 설명
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 |
| [4, 1, 2, 1] | 4 | 2 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4- 총 2가지 방법이 있으므로, 2를 return 합니다.
코딩테스트의 단골 출제유형인 BFS와 DFS를 공부해보았다.
BFS와 DFS의 개념은 대학교 시험기간에 달달달 외워서 잘 알고있었다..^^..
다만, 이론위주의 수업이었다보니 실제로 코드로 구현하며 이해하는 과정이 많이 부족해 이번 기회에 문제를 풀면서 공부를 많이했다.
BFS/DFS의 대표적 문제 유형
- 경로탐색 유형 (최단거리, 시간)
- 네트워크 유형 (연결)
- 조합 유형 (모든 조합 만들기)
BFS - 너비우선탐색
- Queue를 이용해 구현할 수 있다.
- 문제예시: 1과 연결된 1들의 개수가 가장 큰 수를 구하시오.
DFS - 깊이우선탐색
- Stack이나 재귀함수로 구현할 수 있다.
이번 문제는 처음 접해보는 BFS, DFS 문제였기 때문에 오로지 혼자의 힘으로는 풀지 못했다..
아무리 고민해봐도 감을 못잡을것같아 다른사람의 풀이를 보고 과정을 손으로 써가며 이해하였다.
#include <string>
#include <vector>
using namespace std;
int answer = 0;
void DFS(vector<int>numbers, int target, int index, int sum, bool plus)
{
if(plus)
sum += numbers[index++];
else
sum -= numbers[index++];
if(numbers.size() == index)
{
if(sum == target)
answer++;
}
else
{
DFS(numbers,target,index,sum,plus);
DFS(numbers,target,index,sum,!plus);
}
}
int solution(vector<int> numbers, int target) {
DFS(numbers, target, 0, 0, true);
DFS(numbers, target, 0, 0, false);
return answer;
}
풀이는 DFS 방법을 재귀함수로 구현한 코드이다.
주어진 정수 1이 n개만큼 존재할 때 더하거나 빼서 타겟넘버를 만들 수 있는 경우의수를 Count하는 문제이다.
따라서 모든 숫자별로 더하고 빼는경우를 모두 구한 뒤, 타겟넘버와 같은 결과가 나올때만 Count 하면 된다.
따라서 DFS함수의 호출조차 + 하는 경우와, - 하는 경우를 각각 호출해주었다.
재귀함수의 과정을 살짝 이해하기 위한 그림은 아래와 같다.
현재 진행중인 재귀함수의 호출 카운드 = index가 배열의 size와 같다면 최종 sum 값이 target값과 동일한지를 검사한다.