2022/04/19) 10. シーケンスを求めて[再帰関数と完全なナビゲーション(DFS:深度優先ナビゲーション)]

1.質問

2.解決方法

3.正解

        <script>
            function solution(m, arr){         
                let answer=[];
                n=arr.length;
                let ch=Array.from({length:n}, ()=>0); //체크배열(인덱스 n개의 배열을 생성해야 함)
                let tmp=Array.from({length:m}, ()=>0);; //뽑는 걸 담는 거(인덱스 m개의 배열을 생성해야 함)
                function DFS(L){
                    if(L===m){ //D(2)
                        answer.push(tmp.slice()); 
                    }
                    else{
                        for(let i=0; i<n; i++){ //3. DSF(1)의 for문을 돌리자. i가 0일 때 : ch(0)===1이므로  바로 끝 // 4. i가 1일 때 : if문 통과하고 tmp[1]=arr[1] ===> tmp[3,6] //6. i가 2일 때 : if문 통과하고 tmp[1]=arr[2] ===> tmp[3,9]
                            if(ch[i]===0){ 
                                ch[i]=1; 
                                tmp[L]=arr[i]; //1. tmp[0]=arr[0]; ===> tmp[3, ]
                                DFS(L+1); //2. DFS(1); / if문에 해당안되므로 else문으로 와서 for문을 돌려야함 //5. DFS(1+1) ===> 젤 위에 if문에 해당되므로 push. //7. 얘도 마찬가지로 push
                                ch[i]=0; 
                            }
                        } //8. D(1)의 for문은 다 돌았다. 그러므로 이제 DFS(0)의 남은 for문을 돌린다.
                    }
                }
                DFS(0);
                return answer;
            }
            let arr=[3, 6, 9];
            console.log(solution(2, arr));
        </script>

3.感想