bfs나 dfs문제는 무조건 그래프를 그리자.
일단 그리고 나면 어떻게 구현할 지 가닥이 잡힌다.
문제를 보면 규칙이 있다는 걸 알 수 있다.
초기값 즉 0에서 numbers 배열의 요소에 순차적으로 접근해서 더하거나 빼 나가는 것이다.
+,- 두가지 케이스로 나뉜다.
그리고 numbers배열의 마지막 요소까지 계속해서 가지치기 해나간다.
여기서 이진트리 형태를 떠올렸어야 한다.
동시에 탐색법도 생각한다. 어떻게 탐색해야 좋을까... bfs도 가능하다.
하지만 이번에는, 내가 좋아하지만 싫어하는 애증의 재귀를 이용해 dfs로 풀어봤다.
사진은 numbers가 [1,1,1,1]이고 target은 3인 경우이다.
상위노드 0은 초기값이다.
즉 depth1부터 numbers배열의 첫번째 항목에 대한 덧셈과 뺄셈 두가지 케이스가 고려된다.
계속 가지치기를 하다보면 마지막에 하늘색으로 칠해놓은 부분이 target이 3이 된 경우이고, 4가지인 것을 알 수 있다.
- 주의할 점
재귀는 끝맺음이 중요하다. 이를 잘 처리하지 않으면 호출 깊이 초과 에러가 난다. 재귀 탈출 조건을 잘 걸자. 나의 경우 처음에는 중첩된 if문은 잘 구현했으나, 중첩문에서 else파트를 넣어 return이 0인 경우를 지정해주는 것을 빼먹었다.
코드는 아래와 같다.
class Solution {
int cnt = 0;
public int solution(int[] numbers, int target) {
int answer = dfs(-1, numbers, target, 0);
return answer;
}
public int dfs(int depth, int[] numbers, int target, int val) {
if (depth == numbers.length - 1) {
if (target == val) {
return 1;
}
else
return 0;
}
return dfs(depth + 1, numbers, target, val + numbers[depth + 1]) + dfs(depth + 1, numbers, target, val - numbers[depth + 1] );
}
}
...