프로그래머스 - N으로 표현(Lv. 3)

문제 링크

풀이

import Foundation

func solution(_ N:Int, _ number:Int) -> Int {    
    var result = -1
    DFS(0, 0, N, number, &result)
    return result
}

func DFS(_ current: Int, _ currentDepth: Int, _ N: Int, _ number: Int, _ resultDepth: inout Int) {
    if currentDepth > 8 {   // 깊이가 8 이상이라면 패스
        return
    }
    
    // 결과를 만족하고 지금까지 나온 정답의 깊이 보다 더 낮다면 정답을 바꿔치기한다.
    if current == number && (resultDepth == -1 || currentDepth < resultDepth) {
        resultDepth = currentDepth
    }
    
    var attachNum = 0
    for index in 1 ..< 8 {
        attachNum = attachNum * 10 + N  // 자리수를 늘린다
        for operater in Operater.allCases {
            let operatedNum = operater.operate(current, attachNum)
            DFS(operatedNum, currentDepth + index, N, number, &resultDepth) // 계속계속 재귀로 수행
        }   
    }
}

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

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

후기

레벨이 3인데 지문이 엄청 짧네? 꿀빨자!... 라고 잠시 생각했던 문제였다.
곰곰히 생각해도 풀 방법이 떠오르지 않았고 지문을 찬찬히 다시 읽어봤더니 체크할 값이 8 이하..?!
코테에서 8이란 엄청 작은 숫자 아닌가? 이거 모조리 싹다 체크하면 되겠구나! 해서 풀게 되었다.

DFS를 이용해서 모조리 싹다 탐색하면 된다.