Menu

Subscribe

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

HEESOO on Programmers

👀 문제

https://programmers.co.kr/learn/courses/30/lessons/43165

👊 도전

1. 설계

  1. DFS문제이므로 재귀를 이용한다.
  2. 덧셈이나 뺄셈을 이용해 숫자를 계산하므로 이 두가지의 경우에 따라 재귀를 호출하면 된다.
  3. 배열 numbers의 값을 모두 사용하면 숫자가 target과 맞는지 확인한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 *
 * @author HEESOO
 *
 */
 class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer=dfs(numbers, target, 0, 0);
        return answer;
    }
    public int dfs(int[] numbers, int target, int idx, int sum){
        if(idx==numbers.length){//numbers숫자를 모두 사용했다면
            return sum==target? 1 : 0;//target과 같은지에 따라 값 리턴
        }
        else{//덧셈 또는 뺄셈으로 재귀호출. 두 호출 끝의 리턴값을 더해서 answer세야하므로 +
            return dfs(numbers, target, idx+1, sum+numbers[idx])+dfs(numbers, target, idx+1, sum-numbers[idx]);
        }
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 모든 인덱스를 방문해야하므로 DFS를 사용한다.
    • 배열 numbers의 원소을 더하거나 빼서 target이 되는 모든 수를 찾아야하므로 DFS를 이용한다.
    • DFS는 재귀나 스택을 사용하는데, 이 문제에서는 재귀를 썼다.
  2. 인덱스가 마지막 노드까지 방문했느냐에 따라서 다음 재귀를 호출할지 결정한다.
    • 숫자를 모두 사용했다면 지금까지 계산한 sum이 target과 맞는지 확인한다. 맞다면 answer++하기위해 1을 리턴, 아니라면 0을 리턴한다.
    • 아직 다음 노드가 존재할 경우 현재 원소의 값을 sum에 더하거나 뺀다(4번째 파라미터). 그리고 다음 방문을 위해 idx를 하나 증가(3번째 파라미터)시킨다.
    • 이때 재귀호출한 두 함수 사이의 +는, 각 경우에 따른 재귀 리턴값을 모두 더해서 방법의 수를 계산하기 위함이다. 최종적으로 solution함수에서 호출한 dfs(numbers, target, 0, 0)에 총 방법의 수가 리턴된다.

👏 해결 완료!

재귀로 풀어야겠다고 느낌은 왔는데, 안에 파라미터를 어떻게 사용할지, 점화식은 어떻게 작성해야할지 헷갈린다.

참고