[Algorithm: DFS] 프로그래머스 <타겟 넘버>

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java

프로그래머스

 

 

 

---

문제 설명

n개의 숫자가 주어지고, 각 숫자에 + 또는 -를 붙여 target 값을 만드는 경우의 수를 구하는 문제이다.

예시:

numbers = [1, 1, 1, 1, 1]
target = 3

 

가능한 경우의 수: 5개

 

처음 접근

처음에는 단순히

• 더하는 경우
• 빼는 경우

위 2가지를 반복하면서 풀 수 있을 것 같았지만, 모든 경우를 어떻게 탐색해야 할지 감이 잘 오지 않았다.

 

특히 어려웠던 부분은 "어떻게 모든 케이스를 처리할지"였다.

 

---

 

핵심 아이디어

이 문제의 핵심은

각 숫자마다 + 또는 - 두 가지 선택지가 존재한다는 점이다.

 

하나의 숫자를 처리할 때마다

• 더하는 경우
• 빼는 경우

총 2가지 경우로 분기되고, 이 선택이 다음 숫자까지 이어지면서 전체 경우의 수가 만들어진다.

---

 

왜 DFS로 풀어야 할까?

처음에는 단순히 누적합을 계산하는 방식으로 접근하려 했지만 이 문제는 특정 값을 "만드는 방법의 개수"를 구하는 문제다.

 

따라서 

가능한 모든 경우를 빠짐없이 탐색해야 한다

 

 

각 숫자를 기준으로 보면 선택 구조는 다음과 같다.

현재 숫자
├── + 선택
└── - 선택

이 구조가 다음 숫자에서도 반복되면서 전체적으로 보면 이진 트리 형태가 된다.

 

DFS가 적합한 이유

이 문제는 다음과 같은 특징을 가진다.

• 각 단계마다 선택지가 2개 (이진 분기)
• 모든 경우를 탐색해야 함 (완전탐색)
• 순서를 유지하며 진행해야 함 (인덱스)

특히 하나의 경우는 모든 숫자를 다 사용했을 때 완성된다.

따라서 루트 → 리프까지 하나의 경우 완성 → target과 비교

이 흐름이 되는데 이것이 바로 DFS의 동작 방식과 완전히 일치한다.

 

DFS 구조 설계

DFS에서 상태는 딱 두 개만 있으면 된다.

• idx: 현재 몇 번째 숫자인지
• sum: 지금까지 계산된 합

 

종료 조건

 

if (idx == numbers.length) {
    if (sum == target) return 1;
    return 0;
}

 

• 모든 숫자를 다 사용했을 때, target과 같으면 1이고 아니면 0이다.

 

재귀

 

return dfs(idx + 1, sum + numbers[idx], target, numbers)
     + dfs(idx + 1, sum - numbers[idx], target, numbers);

 

현재 숫자를

• 더하는 경우
• 빼는 경우

두 가지를 모두 탐색한다. 

 

---

 

전체 코드

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(0, 0, target, numbers);
    }
    
    private int dfs(int idx, int sum, int target, int[] numbers) {
        
        if (idx == numbers.length) {
            if (sum == target) return 1;
            return 0;
        }

        return dfs(idx + 1, sum + numbers[idx], target, numbers) +
               dfs(idx + 1, sum - numbers[idx], target, numbers);
    }
}

 

 

DFS 흐름 추적

1번 테스트케이스로 흐름 추적을 해보겠다. 

 

numbers = [1, 1, 1, 1, 1]
target = 3

• (idx, sum) 형태로 계속 내려간다.
• 마지막 (idx == length)에서만 판단하면 된다.
• sum == target일 때만 카운트한다. 

 

---

 

 

정리

이 문제에서 가장 어려웠던 점은 다음과 같다.

1. DFS를 떠올리는 것

단순 계산 문제처럼 보이지만 실제로는 모든 경우를 탐색해야 하는 완전탐색 문제였다.

"각 원소마다 선택지가 2개"를 떠올리면서 DFS로 연결했다. 

 

2. 종료 조건 설정

idx == numbers.length

 

여기서만 판단해야 한다는 게 중요했다. 중간에 sum을 체크하면 안 된다.

 

핵심은 

각 숫자마다 + 또는 - 선택 → DFS로 모든 경우 탐색하는 것이다.