프로그래머스 [모음 사전] -BFS/DFS Lv.2

DFS

• DFS를 이용한 완전탐색을 통해 해결한 문제이다.

풀이 전 로직

• A, E, I, O, U 로만 문자열이 구성되는 사전이다.
• 해당 사전은 일정한 규칙을 가지고 있다.
• 5글자가 될 때까지 문자열을 반복하고, 그 뒤엔 맨 뒤 문자열을 제거하고 그 다음 모음(E)을 넣어서 5글자를 만든다.
• 따라서 재귀함수를 이용한 깊이 우선 탐색을 진행하였다.
• 모음은 배열을 만들어 따로 보관하여 해당 배열의 요소들을 순회를 통해 이용하도록 하였다.

코드

function solution(word) {
    const words = ['A', 'E', 'I', 'O', 'U']
    let count = 0
    let answer;
    const dfs = (input) => {
        console.log(input, count)
        // 재귀 종료 조건
        if(input === word) {
            answer = count
        }
        // 이전 재귀로 돌아가는 조건
        if(input.length >= 5) {
            return;
        }
        for(let i = 0; i < words.length; i++) {
            count += 1
            dfs(input + words[i])
        }
    }
    dfs('')
    return answer
}

• 위 코드의 내용을 간략히 살펴보면
  • 모음의 요소들을 배열을 만들어 보관하고,
  • dfs 재귀 함수를 만든다.
  • 종료조건은 글자 수가 5 이상일 때이다. (사전의 문자열은 최대 5글자이기 때문이다.)
  • dfs 함수를 호출할 때마다, count를 1씩 증가시킨다. 즉 사전의 단어를 넘기는 횟수와 같다.
  • for 문 하위에서 dfs를 호출하는데, 이 매커니즘은 다음과 같다.
  • 빈문자열에서 words의 i번째부터 길이가 5가 될 때까지 더한다.
    ex) ' ' + 'A' + 'A' + 'A' + 'A' + 'A'
  • 5글자가 되면,재귀의 종료조건이 발동되어 input은 종료되기 이전인 'AAAA'가 될 것이다.
  • 재귀가 종료되었으니 for문은 다음 모음을 순회한다.
    ex) 'AAAA' + 'E'
  • 위 재귀 과정을 반복하고 문제에서 요구한 word의 순서를 나타내는 answer를 반환한다.

개선 할 사항

• 보다시피 위 코드는 재귀를 통하여 정상적으로 요구사항을 구현은 했지만, 목표 단어인 word를 찾아도 counting만 할 뿐, 계속해서 재귀를 진행한다. 그렇다면 목표 단어를 찾으면 재귀 자체를 중단하는 방법은 없을까?