2022/04/06) 8. 중복순열 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<중복순열>
: 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력한다.

2. 해결방법

1. 우선 중복순열이므로, 중복도 가능하고(=같은 구슬 뽑을 수 있음) 1-2랑 2-1도 가능하다는 걸 알고 있자. 그러므로 경우의 수는 n^2이다.
   3개의 구슬을 2개씩 뽑아야 한다면,
   구슬1을 뽑았을 때(인덱스 0에 1) : 1,2,3 가능(인덱스 1에 1,2,3)
   구슬2를 뽑았을 때(인덱스 0에 2) : 1,2,3 가능(인덱스 2에 1,2,3)
   ... 어 어디서 많이 본 듯한 for문이죠? i를 기준으로 j for문 돌리기!!!

• 왜 다중for문이 아닌 재귀for문으로 코드를 짰을까?
  - 만약 다중for문으로 코드를 짜게 된다면 m의 개수에 따라 코드가 바뀐다. 만약 3개를 뽑아야 한다고 하면, 3개의 for문을 생성해야 한다. 즉, m개의 for문을 생성해야 한다는 말!
  그러나 재귀함수는 L===m의 조건으로 뻗어나가므로, m의 개수가 코드에 영향을 미치지 않는다.

2. tmp를 깊은 복사해야 하는 거 까먹지 않기!! 아직 이해안가는데 나중에 이해되겠지 뭐ㅜ 일단 패스한다.
3. 구슬의 번호로 for문을 돌려서 tmp[L]=i해주고, DFS(L+1);해주기!! tmp!!!
   이 코드는 인덱스 0에 1을 넣고, 1에 1,2,3을 넣는거다!

3. 정답

   <script>
        function solution(n, m){
            let answer=[];
            let tmp=Array.from({length:m}, ()=>0);
            function DFS(L){
                if(L===m){
                    answer.push(tmp.slice());
                }
                else{
                    for(let i = 1; i <= n; i++){
                        tmp[L]=i;
                        DFS(L+1);
                    }
                }
            }
            DFS(0);
            return answer;
        }
        console.log(solution(3, 2));
    </script>