[Algorithm] N으로 표현 (깊이 우선 탐색(DFS))

🖥 문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용 횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

🤔 풀이 방법

By Mre - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=6342841

이 문제는 동적계획법(Dynamic Programming)으로 분류되어 있지만, 깊이 우선 탐색(Depth-First Search)으로 풀었다.
깊이 우선 탐색이란 루트노드에서 부터 시작해서 다음 브랜치로 넘어가기 전에 해당 브랜치를 완벽하게 탐색하는 방법이다.

1. 변수
   • countN : N이 사용된 개수
   • resultN : N을 이용하여 계산한 식의 결과
   • calN : n ~ nnnnnnnn의 수
2. if countN > 8 { return }
   • N은 1이상 9 이하이다. 8을 초과하면(0 ~ 8까지 총 9개를 초과하면) 리턴해준다. 이때 결과는 -1이 된다.
3. if bumber == resultN : number와 계산한 식의 결과 resultN이 같을 경우
   • result == -1 : 아직 계산된 결과가 없어 처음으로 result를 업데이트 해줘야 하는 경우
   • countN < result : 현재 result의 값 보다 더 적은 개수의 N을 사용한 경우
   • 위 두개의 경우에 result를 N이 사용된 개수 countN으로 업데이트 해주고 리턴한다.
4. calN에 n ~ nnnnnnnn의 수를 하나씩 넣어주며 탐색한다.

   for i in 0..<8 { 
    calN = calN * 10 + N
    ...
   }

5. dfs(N, number, countN + 1 + i, resultN + calN, &result) : resultN에 대하여 calN을 +, -, *, / 연산을 수행한다.
   • countN + 1 + i : countN에 N이 사용된 개수를 넘겨준다.
   • resultN + calN : resultN에 계산한 식의 결과를 넘겨준다.

👩🏻‍💻 Swift Code

import Foundation

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

func dfs(_ N:Int, _ number:Int, _ countN:Int, _ resultN:Int, _ result: inout Int) {
    var calN = 0

    if countN > 8 {
        return
    }

    if number == resultN && (result == -1 || countN < result) {
        result = countN
        return
    }

    for i in 0..<8 {
        calN = calN * 10 + N
        dfs(N, number, countN + 1 + i, resultN + calN, &result)
        dfs(N, number, countN + 1 + i, resultN - calN, &result)
        dfs(N, number, countN + 1 + i, resultN * calN, &result)
        dfs(N, number, countN + 1 + i, resultN / calN, &result)
    }
}

 

코딩테스트 연습 - N으로 표현