[Algorithm] 타겟 넘버 (깊이 우선 탐색(DFS))

🖥 문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

🤔 풀이 방법

생각해보자.

[1]로 1을 만드는 방법은 1 한가지이다.
[1, 1]로 2를 만드는 방법은 1 + 1 한 가지이다.
[1, 1, 1, 1, 1]로 3을 만드는 방법은 문제 설명과 같이 다섯 가지이다.
[1, 1]로 3을 만들 수 없기 때문에 0개의 방법이 있다.

깊이 우선 탐색을 진행한다.

깊이 우선 탐색이란 루트 노드에서부터 시작해서 다음 브랜치로 넘어가기 전에 해당 브랜치를 완벽하게 탐색하는 방법이다.
n개의 정수를 모두 사용하여 타겟 넘버를 만들었을 때 answer를 +1 해주고 리턴하였다.
n개의 정수를 모두 사용하였지만 타겟 넘버가 만들어지지 않은 경우 즉시 리턴하여 더이상 탐색을 진행하지 않도록 방지한다.

[1, 1]로 2를 만드는 경우를 보면

-1-1는 n개의 정수를 모두 사용하였지만 타겟 넘버가 만들어지지 않았다. 탐색을 종료한다.
-1+1는 n개의 정수를 모두 사용하였지만 타겟 넘버가 만들어지지 않았다. 탐색을 종료한다.
+1-1는 n개의 정수를 모두 사용하였지만 타겟 넘버가 만들어지지 않았다. 탐색을 종료한다.
+1+1는 n개의 정수를 모두 사용하여 타겟 넘버를 만들었다. answer를 +1 해준다.

모든 탐색이 종료되었고 답은 1이 된다.

👩🏻‍💻 Swift Code

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var answer = 0
    dfs(numbers, target, 0, 0, &answer, "0")
    return answer
}

func dfs(_ numbers: [Int], _ target: Int, _ currentNum: Int, _ index: Int, _ answer: inout Int, _ str: String) {
    if target == currentNum && index == numbers.count {
        answer += 1
        return
    }

    if index >= numbers.count {
        return
    }

    dfs(numbers, target, currentNum - numbers[index], index + 1, &answer, str + "-\(numbers[index])")
    dfs(numbers, target, currentNum + numbers[index], index + 1, &answer, str + "+\(numbers[index])")
}

 

 

코딩테스트 연습 - 타겟 넘버