백준 2023 - Swift

백준 2023 - Swift

https://www.acmicpc.net/problem/2023

 

 

 

해당 문제느 입력의 max가 8인 것을 보아 어떤 알고리즘을

사용하여도 원만하게 풀 수 있는 문제임을 보여주고 있긴 한데요.

저는 DFS, 재귀함수를 이용해서 풀이 했어요.

 

먼저 소수를 정의 해 보자면,

소수 : 1과 자기 자신 이오의 약수가 없는 1보다 큰 자연수

그렇기 때문에 일단 1의 자리에서 소수는 2, 3, 5, 7이 되는 것이고

해당 숫자에서 홀수 (짝수가 되는 순간 != 소수)를 이어 붙여가면서

변화하는 숫자가 소수인지 아닌지 파고 들어가면서 확인해주면 되기 때문에

계속 파고 들어가는 건 DFS 니, DFS를 활용하였습니다.

 

 

소수 판별

먼저 소수인지 아닌지 판별할 수 있는 함수를 만들고

func isPrime(_ number: Int) -> Bool {
    if number < 2 { return false } // 2보다 작다면 소수가 아님
    if number == 2 { return true } // 2면 소수임
    if number % 2 == 0 { return false } // 나눠질 수 있다면(== 짝수라면) 소수가 아님
    
    // 3부터 2씩 증가하면서 제곱근까지의 홀수로 나눠서 홀수인지 아닌지를 확인하기
    for i in stride(from: 3, through: Int(Double(number).squareRoot()), by: 2) {
        if number % i == 0 {
            return false
        }
    }
    return true
}

 

 

DFS

DFS를 정의하여 활용하였습니다.

func DFS(_ number: Int, _ size: Int) {
    if size == n { // 숫자의 자릿수가 입력받은 수의 자릿수와 동일하다면
        // 소수이면 출력
        if isPrime(number) {
            print(number)
        }
        
        return // return 안 하면 나머지 숫자도 계속 돌아서 시간 오래걸림!!
    }
    
    for i in 1...9 {
        // i 중에서 짝수 제외하기
        if i % 2 == 0 { continue }
        
        let nextNumber = number * 10 + i
        // 현재 숫자의 자릿수를 늘리고, 소수인지 확인
        if isPrime(nextNumber) {
            DFS(nextNumber, size + 1)
        }
    }
}

 

 

실행

let n = Int(readLine()!)!

// 1의 자리에서 소수인 수 : 2, 3, 5, 7 의 DFS 실행
DFS(2, 1) // 소수, 해당 소수의 자릿수
DFS(3, 1)
DFS(5, 1)
DFS(7, 1)