프로그래머스 등급2 - 모음사전

모음사전 문제 바로 가기

풀이 날짜: 2026-05-09

baekjoon 알고리즘 문제 풀이

풀이 코드

def solution(word):
    global answer
    answer = 0
    
    words = ["A", "E", "I", "O", "U"]
    
    def dfs(now):
        global answer
        
        if now == word:
            return True
        
        if len(now) == 5:
            return False
        
        for i in words:
            answer += 1
            
            if dfs(now+i):
                return True
        
        return False
    
    dfs("")
    return answer
        
    

문제 핵심

이 문제는 가능한 모든 문자열 조합을 직접 만들어보는 완전탐색 유형 문제였다. 처음에는 단순 구현처럼 보였지만, “A”, “E”, “I”, “O”, “U”를 이용해 길이 5 이하의 모든 단어를 순서대로 생성해야 한다는 점에서 DFS(깊이 우선 탐색)를 활용하는 방식이 자연스럽다고 판단했다. 특히 사전 순서대로 탐색해야 했기 때문에, DFS로 문자열을 하나씩 이어 붙이며 탐색하면 실제 단어 사전을 넘기는 흐름처럼 구현할 수 있었다.

접근 방법 (아이디어)

현재까지 만든 문자열 now를 기준으로, 뒤에 “A”, “E”, “I”, “O”, “U”를 하나씩 붙여가며 재귀적으로 탐색했다. 문자 하나를 추가할 때마다 answer를 증가시켜 “몇 번째 단어인지”를 카운트하도록 구현했다. 그리고 현재 문자열이 목표 단어와 같아지는 순간 True를 반환하여 더 이상 불필요한 탐색이 진행되지 않도록 했다.

이 부분 덕분에 목표 단어를 찾은 이후 재귀 호출을 빠르게 종료할 수 있었다.

구현하면서 중요했던 점

처음에는 DFS를 호출만 하고 결과를 활용하지 않아, 목표 단어를 찾은 이후에도 끝까지 모든 경우를 탐색하는 문제가 있었다. 이를 해결하기 위해:

• if dfs(now+i): return True

형태로 작성하여, 하위 재귀에서 목표 단어를 찾았을 경우 즉시 상위 호출까지 종료되도록 수정했다. 이 과정에서 DFS 재귀 함수의 반환값을 단순 탐색 여부가 아니라 “탐색 종료 신호”로 활용할 수 있다는 점을 이해하게 되었다.

구현 과정에서 헷갈렸던 점

이 문제를 통해 DFS는 단순히 그래프 탐색에서만 사용하는 것이 아니라, 문자열 생성이나 완전탐색 문제에서도 매우 자주 활용된다는 점을 느꼈다. 특히 “모든 경우를 직접 만들어보는 과정” 자체가 DFS와 잘 연결된다는 것을 체감했다. 또한 재귀 함수의 반환값을 적절히 활용하면 불필요한 탐색을 줄이고 효율적으로 구현할 수 있다는 점도 함께 배울 수 있었다.