[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) 타겟 넘버 with Swift

안녕하세요. 오늘은 프로그래머스 2레벨 타겟넘버 문제를 풀어보겠습니다!

 

타겟넘버는 전형적인 dfs문제입니다!

 

각각의 입력이 +와 -일때마다 달라지는 결과가 target과 같으면 결과가 1씩 증가하도록 문제를 하면 되는데요!

 

dfs의 깊이가 입력의 Index로 작용하게 만들어 주시면 됩니다!

 

그리고 depth가 max일때 target과 모든 결과의 합과 비교해서 answer의 증감을 결정해 주시면 됩니다!

import Foundation

var result:Int = 0
var targetResult:Int = 0
var targetDepth:Int = 0
var sourceNumbers:[Int] = [Int]()
var resultsNumbers:[Int] = [Int]()
var answer:Int = 0

func dfs(_ depth:Int) -> Int {
    
    if depth == targetDepth {
        result = 0
        for i in 0..<resultsNumbers.count {
            result += resultsNumbers[i]
        }
        if result == targetResult {
            answer += 1
        }
        return 0
    }
    
    resultsNumbers.append(sourceNumbers[depth])
    dfs(depth+1)
    resultsNumbers.remove(at:depth)
    
    resultsNumbers.append(-sourceNumbers[depth])
    dfs(depth+1)
    resultsNumbers.remove(at:depth)
    
    return 0
}

func solution(_ numbers:[Int], _ target:Int) -> Int {
    targetResult = target
    targetDepth = numbers.count
    sourceNumbers = numbers
    
    dfs(0)
    
    return answer
}