2022/04/19) 10. 순열 구하기 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<순열 구하기>
: 10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력한다.
첫 번째 줄에 자연수 N과 M이 주어진다. 두 번째 줄에 N개의 자연수가 오름차순으로 주어진다.

2. 해결 방법

1. 순서 : DFS(0)의 for문 <i=0일때>! DFS(1)이 호출되므로 DFS(1)의 for문 : i = 0~2 돌리기.
   DFS(1)의 for문이 다 돌면 pop되므로, DFS(0)의 for문 <i=1일때)! 돌리기.
   DFS(0)은 tmp[0]의 값을 결정하고, DFS(1)은 tmp[1]의 값을 결정한다. DFS[2]는 push해준다.

• 흐름
  DFS(0)의 for문 (i = 0,1,2)
  ex ) [3, ][6, ] [9, ]
  DFS(1)의 for문 (i = 0,1,2)
  ex ) DFS(0)의 i가 0일땐, [3, 6], [3, 9] !!!
  DFS(0)의 i가 1일땐, [6, 3], [6, 9]
  DFS(0)의 i가 2일땐, [9, 3], [9, 6]

2. if(ch[i]===0)이면 사용가능하므로, check(1)로 해주고 DFS(L+1);을 해서 push한다. 그리고 돌아올 땐 다시 check(0)으로 초기화해준다.

• arr배열과 ch배열의 관계 : ch배열은, arr배열에 속한 인덱스가 이전에 사용됐던건지의 유무를 체크한다. 그러므로 인덱스 개수가 같다. 그러므로 한 for문에서 i를 공유해서 사용할 수 있다.

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. DFS(1)의 for문은 다 돌았다. 그러므로 이제 DFS(0)의 남은 for문(i=1,2)을 돌린다.
                    }
                }
                DFS(0);
                return answer;
            }
            let arr=[3, 6, 9];
            console.log(solution(2, arr));
        </script>

3. 소감

거의 한 시간 넘게 뚫어져라 쳐다보고 있으니 이해가 가는군..