글 쓰는 시간

DFS

프로그래머스 타겟 넘버 문제를 통해 처음 dfs 를 접해보았다. 

dfs 가 무엇인가 맛보고 이해하기에 좋은 문제인것 같다.

풀이

1. 깊이 우선 탐색 알고리즘을 이용하여 탐색을 시작한다.
2. 처음 노드(depth = 0)부터 마지막 노드(depth = numbers.length)까지 탐색을 수행
3. 마지막 노드까지 탐색했을 때 타겟 넘버와 결과값이 같으면 정답 카운트 1 증가

깊이 우선 탐색 알고리즘

public void dfs(int[] numbers, int depth, int target, int sum) {
    // numbers : 알고리즘을 수행할 대상 배열
    // depth : 노드의 깊이
    // target : 타겟 넘버
    // sum : 이전 노드까지의 결과값
}

최종 코드

public class TargetNumber {
    // 정답 카운트
    // 초기값 0부터 시작
    int answer = 0;

    // 깊이 우선 탐색
    public void dfs(int[] numbers, int depth, int target, int sum) {
        // 마지막 노드까지 탐색했을 때 sum == target 이면 정답 카운트 1 증가
        if (depth == numbers.length) {
            answer += sum == target ? 1 : 0;
        } else {
            // depth 가 0 부터 numbers.length 까지 numbers[depth] 값을 +, - 를 동시에 진행한다.
            dfs(numbers, depth +1, target, sum + numbers[depth]);
            dfs(numbers, depth +1, target, sum - numbers[depth]);
        }
    }

    public int solution(int[] numbers, int target) {
        // 깊이 우선 탐색 시작
        // depth 초기값은 0
        dfs(numbers, 0, target, 0);
        return answer;
    }
}

참고자료)