[백준] (Swift) 1759번 - 암호 만들기 (두번째풀이) (feat. DFS, 백트래킹, 골드5)

🟠 문제

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

1759번: 암호 만들기

 

🟠 나의 풀이

문제를 같은 부류끼리 모아 풀어서 그런가, 확실히 문제를 보고 어떻게 풀지 딱 떠올랐다. 예전에는 안그랫는데,,, 역시 한 분야만 죽어라 파고, 그 분야에 익숙해질때까지 문제들을 눈에 넣는게 중요한것 같다.

일단, 이 문제의 핵심은 다음과 같다.

1. 오름차순으로 출력되어야하기 때문에, 오름 차순으로 정렬된 배열을 이용해야하고, 앞에 지나왔던 배열요소들은 보지 않도록 만들어주어야한다. 이 부분은, 매개변수로 index 값을 넘겨주면서, 지금 보다는 하나 뒤에 있는 요소만 바라볼 수 있도록 만들어줄 것이다.
2. 중복을 허용하지 않기 때문에 visited 배열을 만들어서 하나씩 방문처리를 해주었다.
3. dfs를 재귀로 돌리면서 조건으로 확인해야하는 것이 3가지가 있다. 모음이 한개 이상 존재하는지, 자음이 두개 이상 존재하는지, 그리고 입력받은 L과 길이가 같은지! 이렇게 세가지를 판단해주어야한다.

이 풀이와 비슷한, 더 자세한 해석을 보고 싶다면 아래 문제를 참고해보자.

https://didu-story.tistory.com/381

[백준] (Swift) 18290번 - NM과 K(1) (feat. 브루트포스, DFS, 백트래킹)

 

🟠 정답코드

import Foundation

var lc = readLine()!.split(separator: " ").map{ Int($0)! }
var l = lc[0]
var c = lc[1]
var aeiou = ["a", "e", "i", "o", "u"]
var arr = readLine()!.split(separator: " ").map{ String($0) }.sorted(by: <)
var visited = Array(repeating: false, count: c)
var password = [String]()

private func dfs(index: Int) {
    // 최소 모음 한개 이상, 최소 자음 두개 이상
    if password.count == l {
        var containAeiou = false
        var consonantCnt = 0

        for i in password {
            if aeiou.contains(i) {
                containAeiou = true
            } else {
                consonantCnt += 1
            }
        }

        if consonantCnt >= 2, containAeiou {
            print(password.joined(separator: ""))
        }
        return
    }

    for k in index..<c {
        if !visited[k] {
            visited[k] = true
            password.append(arr[k])
            dfs(index: k)
            visited[k] = false
            password.removeLast()
        }
    }
}

dfs(index: 0)