[프로그래머스] 타겟넘버 Swift (DFS)

✅ 문제를 풀다가 그냥 한번 적어보고 싶어서..

 

난이도 자체는 크게 어렵지는 않았는데, 알고리즘을 놓은지 오래되어서 머릿속으로 설계가 되어도 코드를 어떻게 짜야하는지 감이 잡히지가 않았다 ㅜㅜ

게다가 언어도 C -> Python3 -> Swift5로 변경해서, 쉽게 떠오르지가 않았음.

 

결국 그림을 그리면서 어떻게 할지 설계를 했었는데

머릿속으로 하는게 진짜 잘하는 거라던데 ㅜ

 

✅ 코드

//
//  File.swift
//  algorithm
//
//  Created by Hamlit Jason on 2021/08/08.
//

/* 타겟넘버
 https://programmers.co.kr/learn/courses/30/lessons/43165
 DFS 사용
 */

import Foundation

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

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

//print(solution([1, 1, 1, 1, 1], 3))

 

 

여기서 내가 헷갈렸던 부분이 divide and conquer(분할정복) 방식에 사로잡혀서, return시 위로 올라가서 또 다른 계산을 진행해야한다고 생각했었는데, 최종에 다다르기 까지 sum값을 계속 계산하며 if에서 return될경우 바로 solution쪽으로 이동하여 값을 산출하게 된다.

재귀의 로직을 보자면...

이런 방식으로 진행된다. 그리고 최종적으로 값을 다 구한 뒤에 ans값을 반환하여 답을 찾게 된다.

 

https://github.com/lgvv/Algorithm_Swift/blob/main/algorithm/Programmers/%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84.swift