[Algorithm] 모음사전

문제설명

모음사전은 'A', 'E', 'I', 'O', 'U' 순으로 만들어지는 트리 구조에서 주어진 word가 등장하는 차례를 반환하는 문제이다.

테스트케이스의 설명을 보면 다음과 같은 형태의 트리를 DFS로 순회하며 만들어지는 문자열임을 확인 할 수 있다.

"A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU", "AAAE", "AAAI"

DFS를 사용하여 순차적으로 만들어지는 문자열의 모든 경우의 수를 재귀적으로 확인하고 주어진 문자열과 일치할 경우를 찾으면 문제를 해결할 수 있다.

### DFS(깊이우선탐색)

가장 깊은 곳까지 방문한 후 최근 방문한 지점을 다시 돌아와 탐색하는 방법이다.

재귀를 이용한 방법이랑 스택을 이용한 방법이 존재한다.

문제해결

function solution(word) {
    // 사전을 만들 알파벳 배열과 word의 차례를 선언 및 초기화 할당
    let library = ['A', 'E', 'I', 'O', 'U'];
    let count = 0,
        endFlag = false;
    
    function dfs (newWord) {
        // 3. 루프를 끊기 위해 조건 설정 : 정답을 찾으면 재귀 종료
        if (word === newWord || endFlag) {
            endFlag = true;
            return;
        }
        // 2. 루프를 끊기 위해 조건 설정 : 만들 단어의 길이를 넘기면 재귀 종료
        if (newWord.length > 5) return;
        // 4. 루프가 실행될 때 카운트
        count++;
        for (let i = 0; i < library.length; i++) {
            dfs(newWord + library[i])
            // 1. ''.'A','AA','AAA','AAAA','AAAAA'... 무한 재귀가 생성
        }
    }
    // 카운트 1 : dfs(A) 부터 실행
    dfs('');
    return count;
}