[Java] 프로그래머스: 타겟 넘버

 

DFS

모든 노드를 방문해야 노드들의 합이 타겟 넘버와 같은지 확인할 수 있다.

[그래프 탐색] BFS / DFS

[그래프 탐색] BFS / DFS

 

전체 풀이

class Solution {
    
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, 0, target, 0);

        return answer;
    }
    
    public void dfs(int[] numbers, int depth, int target, int sum) {

        if (depth == numbers.length) { // 마지막 노드인 경우
            if (target == sum) {
                answer++;
            }
        } else { // 탐색할 노드가 남은 경우, 두 가지 경우로 깊이 우선 알고리즘 실행
            dfs(numbers, depth + 1, target, sum + numbers[depth]); // 이웃 노드 방문: +
            dfs(numbers, depth + 1, target, sum - numbers[depth]); // 이웃 노드 방문: -
        }
    }
}

• 마지막 노드까지 탐색했을 경우
  • target 수와 sum이 같은지 확인한다.
• 탐색할 노드가 남은 경우
  • 깊이를 나타내는 depth에 1을 더하고, 현재까지의 sum과 이웃 노드를 더한 경우와 뺀 경우 두 가지 경우로 나누어서 dfs를 반복한다.