프로그래머스 - 타겟 넘버(Lv. 2)

문제 링크

풀이

import Foundation

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

// index: DFS의 Depth, value: 현 깊이까지의 결과, count: 타겟 넘버 만족 횟수
func DFS(_ index: Int, _ value: Int, _ numbers: [Int], _ target: Int, _ count: inout Int) {
    if index == numbers.count { // 이제 결과를 도출할 시간
        if value == target {    // 타겟 넘버를 만족한다면
            count += 1
        }
        return
    }
    
    for operater in Operater.allCases {
        let currentValue = operater.operate(value, numbers[index])
        DFS(index + 1, currentValue, numbers, target, &count)
    }
}

// 연산을 수행할 녀석
enum Operater: CaseIterable {
    case plus
    case minus

    func operate(_ arg: Int, _ N: Int) -> Int {
        switch self {
            case .plus:
                return arg + N
            case .minus:
                return arg - N
        }
    }
}

후기

지문을 읽자마자 바로 어떻게 풀어야할지 머리속에서 그려진 문제.
하도 BFS DFS를 사용해보다 보니 10분컷 해버렸다.
깊이 넓이 우선탐색 관련 문제 중 가장 기본적인 문제 아닌가 싶다.