완전탐색 Level 2 모음사전 - python (프로그래머스)

소스 코드

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

 

 

풀이

해당 문제는 dfs/bfs를 접해보지 않았기 때문에 기존에는 중복순열을 사용하여 가능한 모든 단어의 조합을 구한 다음 index를 사용하여 몇번째에 위치하는지 찾았다.

 

하지만 또 다른 풀이를 살펴보는 도중 dfs를 사용하는 방법도 있어 dfs에 대한 개념을 익힌 다음 위 문제에 적용해 보았다.

dfs에서 중요한 점은 재귀를 사용하기 때문에 해당 함수를 다시 호출할 때 어떤 값을 넘겨줄지와 종료 조건을 잘 설정해야 한다.

위 문제에서 최초로 dfs를 호출하는 부분에서 word_list를 쭉 순회해가며 해당 문자로 문자열을 만들도록 스타트를 끊는다. 그리고 dfs 함수 내에서도 word_list를 순회해가며 최초로 받은 문자에 붙여서 문자를 재귀함수에 넘겨준다.

 

dfs의 탈출 조건은 원하는 목표 문자를 만들었을 경우 또는 word의 길이가 5글자가 되었을 경우이다.