[Swift][DFS] 백준 1759번 (암호만들기)

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

 

코드설명 : 

N과M(8) 문제로 선행학습을 하고 풀면 정말 효율적일거같다. 안푸셨다면 풀고오시길...

 

N과M(8)에서 바뀐부분

1. 숫자가 아닌 알파벳이라는 점

2. for문을 이용하여  자음이 2개이상, 모음이 1개이상인지 판별 

 

후기 : 우연찮게 이 문제를 접하게됬는데 N과M(8)과 거의 유사한문제다.. 자음 2개이상과 모음1개이상이 들어갔는지만 판별하면 되는 문제였다.. 골드문제를 처음으로 15분도안걸려서 풀었다. 시간초과가 날거같았는데, 2초인거보고 안심... 

let LC = readLine()!.split(separator: " ").map{Int(String($0))!}
let L = LC[0]
let C = LC[1]
let arr = readLine()!.split(separator: " ").map{String($0)}.sorted()
let vowel = ["a","e","i","o","u"]
let consonant = ["b","c","d","f","g","h","j","k","l","m","n","p","q","r","s","t","v","w","x","y","z"]
var depth = 0
var visited: [Bool] = Array(repeating: false, count: C)
var result: [String] = []

func dfs(_ depth: Int, _ start: Int){
    if depth == L{
        var isprinted = false
        for i in vowel{
            if result.contains(i){
                isprinted = true
            }
        }
        var count = 0
        for j in consonant{
            if result.contains(j){
                count += 1
            }
        }
        if count >= 2 && isprinted{
            print(result.joined(separator: ""))
        }
        return
    }
    
    for i in start..<C{
        if !visited[i] {
            visited[i] = true
            result.append(arr[i])
            dfs(depth + 1, i)
            visited[i] = false
            result.removeLast()
        }
    }

}

dfs(depth, 0)