[Programmers] 모음사전 (완전탐색 - DFS Lv. 2) - Python

1. 문제

---

모음사전

2. 풀이

---

코드

def dfs(target_word, current_word):
    vowels = ['A', 'E', 'I', 'O', 'U']
    temp_word = current_word
    
    if current_word == target_word:
        return count
    
    if len(current_word) >= 5:
        return -1
    
    for vowel in vowels:
        current_word += vowel
        count += 1
        result = dfs(target_word, current_word)
        if result != -1:
            return result
        current_word = temp_word
    
    return -1

def solution(word):
    global count
    current_word = ""
    count = 0
    answer = dfs(word, current_word)
    return answer

입력 및 출력

word = "AAAE"	

>> 10

3. 로직

---

1. vowels 리스트에는 모음 'A', 'E', 'I', 'O', 'U'를 저장한다.

2. temp_word 변수에는 현재 단어 current_word를 저장한다.

3. current_word와 target_word가 동일한 경우, 이 단어가 사전에서 몇 번째 단어인지 저장된 count를 반환한다.

4. current_word의 길이가 5 이상인 경우 더 이상 모음을 추가할 수 없으므로 -1을 반환한다.

5. vowels 리스트의 각 모음에 대해 다음 작업을 수행한다.

   • current_word에 모음을 추가하고 count를 1 증가시킨다.

   • dfs 함수를 재귀적으로 호출하며 가능한 탐색을 모두 진행한다.

   • 반환된 결과(result)가 -1이 아닌 경우, 목표 단어를 찾았다는 의미이므로 해당 결과를 바로 반환한다.

   • 다음 재귀 호출을 진행하기 위해서 current_word를 재귀 호출 전의 상태인 temp_word로 되돌린다.

6. 모든 반복이 완료되고도 목표 단어를 찾지 못한 경우, -1을 반환한다.

4. 그림

---