[Swift][DFS][LV_1][프로그래머스] 소수 만들기

요구능력 : 백트래킹에 대한 이해

 

코드설명 : 

 

풀이는 살펴보니 여러가지 각양각색이다.

나는 N개의 배열에서 3개를 뽑아내서 백트래킹으로 문제를 풀어냈다.

백준의 N과M을 이해하고온다면 문제를 쉽게 풀 수 있다.

 

1. 3개를 뽑아내기위한 부분

for i in start..<nums.count {
            if !visited[i]{
                visited[i] = true
                result += nums[i]
                dfs(depth + 1, i)
                result -= nums[i]
                visited[i] = false
            }
        }

 

2. 3개를 뽑아내고 소수를 판별하는 부분

if depth == 3{
            for i in 2..<result {
                if result % i == 0 {
                    isNumber = false
                }
            }
            if isNumber{
                answer += 1
            }
            isNumber = true
            return
        }

 

후기 : 프로그래머스 문제는 이전에 한번밖에 풀어본적이 없는데 LV1이 백트래킹이라니 허허..

func solution(_ nums:[Int]) -> Int {
    var answer = 0
    var visited = Array(repeating: false, count: nums.count)
    var result = 0
    var isNumber = true
    
    func dfs(_ depth: Int, _ start: Int){
        if depth == 3{
            for i in 2..<result {
                if result % i == 0 {
                    isNumber = false
                }
            }
            if isNumber{
                answer += 1
            }
            isNumber = true
            return
        }
        for i in start..<nums.count {
            if !visited[i]{
                visited[i] = true
                result += nums[i]
                dfs(depth + 1, i)
                result -= nums[i]
                visited[i] = false
            }
        }
    }
    dfs(0, 0)
    return answer
}