[프로그래머스] DFS / BFS - 타켓 넘버

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

입력 & 출력

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때
숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 출력하시오.

풀이

친절하게 DFS / BFS로 푸는 문제임을 알려주었다
숫자들을 numbers의 크기만큼 반복해서 원하는 수를 만들 수 있는지 확인한다

이 반복을 depth로 센다
depth == numbers.count 가 될 때까지 반복하며, numbers[depth] 값을 총합에 더하고 빼는 과정을 거친다
만약 depth == numbers.count이라면, 또 총합이 원하는 수와 맞다면 푸는 방법(count)이 하나 추가된다

 

Swift 전체 코드

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var count = 0
    
    func dfs(_ depth : Int, _ sum : Int){
        if depth == numbers.count {
            if sum == target {
                count += 1
            }
            return
        }
        
        dfs(depth + 1, sum + numbers[depth])
        dfs(depth + 1, sum - numbers[depth])
    }

    dfs(0,0)
    
    return count
}