코딩테스트 연습 - 모음사전

문제 풀이 아이디어

사전이 진행되는 방식을 보면 딱 DFS가 떠오릅니다. 각 모음을 하나의 경로로 보면 “A” → “AAAAA”의 최대 깊이까지 경로 탐색을 하고 “AAAAE”로 최대 깊이에서 다음 경로를 탐색합니다. 그리고 나서 “AAAAX”를 모두 탐색하고 나서 “AAAE”부터 다시 탐색을 시작합니다. DFS, 즉 “깊이" 우선 탐색과 동일한 순서로 사전이 구성되는 것이죠. (만약에 A → E → … → U → AA라면 BFS, “너비” 우선 탐색이 되겠죠?)

dfs가 실행되는 횟수를 셀 때 주의할 점이 dfs를 실행하기 전에 count를 + 1 해야 한다는 점입니다. dfs를 실행한 이후에 + 1을 하면 dfs가 안에서 실행된 dfs들이 모두 리턴된 이후에 + 1되기 때문입니다.

코드

import Foundation

func solution(_ word:String) -> Int {
    // 반복문을 위한 배열
    let vowels = ["A", "E", "I", "O", "U"]
    
    // dfs할 때마다 + 1할 변수
    var cnt = 0
    
    // 정답
    var ans = 0
    
    func dfs(_ s: String) {
        
        // 현재 탐색한 문자열이 word와 같으면 ans를 cnt로 업데이트
        if s == word { ans = cnt; return }
        
        // s의 길이가 5보다 짧을 때만 뒤에 알파벳을 붙임
        if s.count < 5 {
            for i in 0..<vowels.count {
                cnt += 1
                dfs(s + vowels[i])
            }
        }
    }
    
    dfs("")
    
    return ans
}