[Algorithm] 프로그래머스 - 모음사전

🥸 문제 소개

🧑🏻‍💻 문제 풀이

사전을 순서대로 만들어 나가면서 target이 현재 추가된 단어와 같다면 값을 리턴하게 만들었다. 사전을 만들어 나가는 과정은 재귀함수를 활용하여 구현했다.

func solution(_ target: String) -> Int {
    let vowels = ["A", "E", "I", "O", "U"]
    var found = false
    var answer = 0

    func dfs(_ word: String) {
        if word.count > 5 || found { return }
        
        answer += 1
        
        if word == target {
            found = true
            return
        }
        
        vowels.forEach { dfs(word + $0) }
    }

    vowels.forEach { dfs($0) }
    
    return answer
}

이 문제는 사실 전위 탐색과도 깊은 연관이 있다. 아래와 같은 구조가 있을 때, 전위 탐색은 A → B → D → E → C 의 과정을 거치는데 이것이 여기서 말하는 사전의 순서와 같다.

       A
      / \
     B   C
    / \
   D   E

아래와 같이 나쁘지 않은 결과를 얻을 수 있었다~ 😇