완전탐색_모음사전

생각보다 시간이 많이 걸렸던 문제,, 

 

접근 방법

완전탐색을 사용해야 한다. 문제의 예시에서 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. 의 순서로 탐색이 진행되기 때문에 재귀의 방식을 활용해야 함을 알 수 있다.

 

def solution(word):
    global answer
    global cnt
    moeum = ['A', 'E', 'I', 'O', 'U']
    dfs('',moeum,word)
    return answer

answer = 0
cnt = 0 
flag = False

def dfs(k,moeum,word):
    global answer
    global cnt
    global flag
    print(k)
    
    # 정답여부 변수
    if flag:
        return
    
    # 정답과 같으면 return
    if k == word:
        print(cnt)
        answer = cnt
        flag = True
        return True
    
    # 길이가 모음사전의 길이와 같아지면 return
    if len(k) == 5:
        return
    
    temp = k
    # 재귀
    for n in moeum:
        temp += n
        cnt+=1
        dfs(temp,moeum,word)
        temp = temp[:-1]

flag 변수 적용

flag 변수 적용 안함

 

처음 flag 변수를 적용하지 않았을 때도 정답은 나온다. 하지만 log를 출력했을 때, 정답을 찾았음에도 모든 변수를 탐색하고 종료되는 것을 알 수 있다. 개선을 하고자 flag 변수를 두어 재귀 호출 중 정답을 발견하면 flag 변수를 True 값으로 만들어 이후 탐색에서는 dfs 호출 후 바로 return 만 되도록 구현하였다. 사실 이 방식도 정답을 찾은 후 바로 모든 재귀가 종료되지는 않지만, 정답을 찾기 위해 호출한 재귀의 횟수만큼만 추가 시행이 된 후 프로그램이 종료되었다.