DFS
Overview
DFS(Depth First Search)
practice
import (
"math"
"strconv"
)
type set map[interface{}]struct{}
func (s set) Insert(v interface{}) {
s[v] = struct{}{}
}
func (s set) length() int {
return len(s)
}
func solution(numbers string) int {
primes := set{}
depth := make([]bool, len(numbers), )
dfs(numbers, "", depth, primes)
return primes.length()
}
func dfs(numbers string, checkNumber string, depth []bool, primes set) {
if len(numbers) == len(checkNumber) {
return
}
for i := range numbers {
if depth[i] {
continue
}
depth[i] = true
nextCheckNumber := checkNumber + string(numbers[i])
if isPrimeNumber(nextCheckNumber) {
primes.Insert(nextCheckNumber)
}
dfs(numbers, nextCheckNumber, depth, primes)
depth[i] = false
}
}
func isPrimeNumber(stringNumber string) bool {
if stringNumber[0] == '0' {
return false
}
number, _ := strconv.Atoi(stringNumber)
if number <= 1 {
return false
}
sqrtNum := int(math.Sqrt(float64(number)))
for i := 2; i <= sqrtNum; i++ {
if number % i == 0 {
return false
}
}
return true
}
reference
https://programmers.co.kr/learn/courses/30/lessons/42839
Reference
この問題について(DFS), 我々は、より多くの情報をここで見つけました https://velog.io/@sehyoung/DFS-0x40vrxnテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol