[백준] 2922번 : 즐거운단어

2922번: 즐거운 단어

해당문제는 완전탐색문제로 “생각의 틀”을 벗어나 문제를 풀게 만든 문제입니다.

처음에 문제를 접할때 자음과 모음을 모두 확인해보면서 문제를 해결하려고 접근하였습니다. 그러나 이 방법은 즐거운 단어를 만드는 단어를 구하는 위한 과정이었고, 문제는 “경우의 수”만 구하면 된다는 것 입니다.

모음이 연속해서 3번, 자음이 연속해서 3번이 나오지 않을 조건을 탐색조건으로 분기시켜 깊이우선탐색으로 문제를 해결 할 수 있습니다. 예를들어 이전에 모음이 2번 나왔을경우 그다음 탐색조건은 자음이 나와야하며, 이전에 자음이 2번 연속 나왓을경우 무조건 모음으로 탐색해야합니다.

mo = {'A','E','I','O','U'}

word = input()

def dfs(mocnt, jacnt, lcnt, depth):
    if mocnt >= 3 or jacnt >= 3:
        return 0
    
    if depth == len(word):
        if lcnt:
            return 1
        else:
            return 0
    
    result = 0
    if word[depth] == '_':
        # 모음일때
        result += dfs(mocnt+1,0,lcnt, depth+1) * len(mo)
        # L을 제외한 자음일때
        result += dfs(0,jacnt+1,lcnt, depth+1) * (25 - len(mo))
        # L일때
        result += dfs(0,jacnt+1, lcnt+1, depth+1) * 1
    else:
        if word[depth] in mo:
            result += dfs(mocnt+1,0, lcnt, depth+1)
        else:
            if word[depth] == 'L':
                result += dfs(0, jacnt+1, lcnt+1, depth+1)
            else:
                result += dfs(0, jacnt+1, lcnt, depth+1)
        
    return result
            

print(dfs(0,0,0,0))