[PGM] 모음사전 / Level 2 / 60분+

[kledyu]

flag를 사용하지 않고 시도하다가 결국, 검색의 도움을 받았습니다.

그러나 flag의 존재의 유무가 왜 정답을 이끄는 이유인 지 궁금합니다.. @cdm1263

function solution(word) {
    const alphabet = ['A', 'E', 'I', 'O', 'U'];
    let count = 0;

    function DFS(target) {
       // 입력 값이 word와 같거나 혹은 입력 값의 길이가 5를 초과하면 DFS 종료 
        if (target === word || target.length > 5)  return;

        count += 1;

        for (let i = 0; i < alphabet.length; i++) {
            DFS(target + alphabet[i]);
        }
    }

   DFS('');

   return count;
}

/* 최초 코드 */
/////////////////////////////////////////
/* 이후 코드 */

function solution(word) {
    const alphabet = ['A', 'E', 'I', 'O', 'U'];
    let count = 0;
    let flag = false

    function DFS(target) {
        if (target === word || flag) {
           flag = true;
           return;
       }

       if (target.length > 5) return;

        count += 1;

        for (let i = 0; i < alphabet.length; i++) {
            DFS(target + alphabet[i]);
        }
    }

   DFS('');

   return count;
}

[cdm1263]

flag를 사용하지 않고 시도하다가 결국, 검색의 도움을 받았습니다.

그러나 flag의 존재의 유무가 왜 정답을 이끄는 이유인 지 궁금합니다.. @cdm1263

function solution(word) {
    const alphabet = ['A', 'E', 'I', 'O', 'U'];
    let count = 0;

    function DFS(target) {
       // 입력 값이 word와 같거나 혹은 입력 값의 길이가 5를 초과하면 DFS 종료 
        if (target === word || target.length > 5)  return;

        count += 1;

        for (let i = 0; i < alphabet.length; i++) {
            DFS(target + alphabet[i]);
        }
    }

   DFS('');

   return count;
}

/* 최초 코드 */
/////////////////////////////////////////
/* 이후 코드 */

function solution(word) {
    const alphabet = ['A', 'E', 'I', 'O', 'U'];
    let count = 0;
    let flag = false

    function DFS(target) {
        if (target === word || flag) {
           flag = true;
           return;
       }

       if (target.length > 5) return;

        count += 1;

        for (let i = 0; i < alphabet.length; i++) {
            DFS(target + alphabet[i]);
        }
    }

   DFS('');

   return count;
}

정확한 답변이 될지는 모르겠지만 제 견해를 말씀드리겠습니다!

DFS 함수 내부의 for문으로 DFS 함수가 제귀적으로 실행되면서 가장 깊은 곳부터 탐색하던 도중 정답을 찾게 된 순간 동작하고 있던 모든 DFS를 멈추기 위해 모든 DFS 함수가 동시에 참조 가능한 flag라는 값을 두어서 'flag가 true임이 탐지된 순간, 모든 DFS를 중지해라' 라는 형태로 진행이 되는 것 같습니다!

만일 flag라는 최상단 변수 없이 기존 코드로 진행했을 경우, 정답을 찾은 DFS함수를 제외한 나머지 병렬로 진행되는 DFS 함수들은 계속해서 탐색을 하게 되는 것으로 보입니다!

flag = true 바로 상단에 console.log('DFS 중지!') 를 입력해 몇 개의 DFS 함수가 동작을 멈추는지 확인 해 보시면 이해하기 쉬우실 듯 합니다!