순열 구하기(DFS)

코드

  function solution(m, arr) {
    let answer = [];
    let n = arr.length;

    let ch = Array.from({ length: n }, () => 0);
    let temp = Array.from({ length: m }, () => 0);

    function DFS(L) {
      if (L === m) {
        answer.push(temp.slice());
      } else {
        for (let i = 0; i < n; i++) {
          if (ch[i] === 0) {
            ch[i] = 1;
            temp[L] = arr[i];
            DFS(L + 1);
            ch[i] = 0;
          }
        }
      }
    }

    DFS(0);

    return answer;
  }

해결 방법

1. ch는 각 자연수가 중복되는지를 체크하는 배열이고, temp는 m개씩 뽑기 때문에 자연수 m개를 담는 배열이다. 

2. DFS(L)

L(level)은 temp에 현재 담긴 자연수의 개수를 의미한다.

 

-if (L === m)

L과 m이 같다면 answer에 temp를 slice로 깊은 복사를 하여 넣어준다.

 

-L이 m보다 작은 경우

for문을 n만큼 반복하면서 ch[i]가 0이면 ch[i]를 1로 바꿔준다. 그 후 temp[L]에 arr[i]를 넣어주고 DFS(L + 1)을 해서 가지를 뻗는다.

그리고 ch[i] = 0을 하는 이유는 뻗은 가지를 다 수행하면 다시 위로 올라가서 다른 가지를 뻗어야 하기 때문이다.