[DFS] 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=python3

프로그래머스

 

본 문제는 아래와 같이 접근을 시도하였다. 

사진에서 보이는 것처럼 
A
AA
AAA
AAAA
AAAAA -- 종점 도착
AAAAE

이렇게 쭉 종점까지 선회하는 방법으로 searching하기 때문에 깊이 우선 탐색 전략을 채택한다. 

이렇게 종점에 도착해도 여전히 사전의 순서는 진행되어야 하므로 이를 나타내는 변수 cnt는 누적이 되어야 한다.

따라서 global 변수를 활용해서 이를 누적하였다.

따라서 이를 구현한 코드는 다음과 같다. 특별히 for loop에서 이미 U에서 끝내는 조건이 있기에 굳이 종료 조건으로 U일 떄를 넣어줄 필요는 없다 (주석 처리한 if문처럼)

memo = {}
### global 변수 쓰는 거에 익숙해지자!
global cnt
cnt = 0

def DFS(curr) :
    ### global 변수 쓰는 거에 익숙해지자!
    global cnt

    if curr != '' :
        memo[curr] = cnt

        #if len(curr) == 5 or curr[-1] == 'U' :
        #    return
        
        ### 종료 조건은 여기면 충분!
        if len(curr) == 5 :
            return
    
    ### 어차피 반복문 마지막에서 U에서 끝나므로 종료 조건에는 필요 없음
    for now in 'AEIOU' :
        cnt += 1
        DFS(curr+now)
        
def solution(word) : 
    DFS('')
    return memo[word]