DFS - 순열 구하기

순열을 구하는 코드에 대해서는 이미 숙지가 되어있다.

하지만 기존에 외웠던 코드는 n개중에 n개를 순서를 고려해서 나열하는 경우의 수를 구할 때는 유용하지만 n보다 작은 수를 뽑아 순서를 고려해 나열하는 방법은 배열을 잘라줘야한다는 번거로움이 따른다.

지금 정리하는 방법은 구현 과정도 이해가 잘되고 n보다 작은 수를 뽑는 경우에도 배열을 자를 필요없이 곧바로 정답을 리턴하다는 것에 장점이 있다.

 

예를 들어 3 6 9 라는 수열이 주어지고, 이 숫자들 중 2개를 뽑아 순서를 고려해 나열하는 경우의 수를 구해보자.

우선 준비물이 필요하다. 바로 체크배열과 tmp라는 배열이다. 체크배열은 탐색한 요소를 체크하는 역할을 하고, tmp는 뽑은 요소를 넣어주는 배열이다. 체크배열이 필요한 이유는 중복순열과 다르게 중복을 허용하지 않기 위해서이다.

 

먼저 go(0)을 호출한다. go는 레벨을 인자로 받는데 깊이의 단계라고 생각하면 된다.

요소가 3, 6, 9이므로 for문을 돌면서 하나씩 체크한다. 먼저 3이 들어올 것이고 3은 체크배열에 체크되지 않았으므로 체크해준다. 그리고 tmp에 3을 넣어준다. 그리고 레벨을 하나 더해주고 다시 for문을 돌면서 3, 6, 9를 체크한다.

3은 이미 체크가 되어있기 때문에 넘어가고 6은 체크가 되어있지 않기 때문에 6을 체크하고 6을 tmp에 넣어준다.

그리고 다시 레벨을 하나 올리고 재귀함수를 실행할 것인데 이미 2개를 다 뽑은 상황이다. 이 상황은 레벨이 우리가 뽑으려는 갯수와 일치할 때이다. 따라서 이때는 tmp에 저장된 수를 출력한다. 그리고 원복의 과정과 똑같이 체크를 해제해야한다.

6의 체크가 해제되고 9로 넘어가 9는 체크되어있지 않으므로 9를 체크하고 2개를 다 뽑았으니 3 9를 출력한다.

코드를 보면 더 이해가 잘될 것이다.

let input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
let [n, m] = input[0].split(' ').map(Number);
let arr = input[1].split(' ').map(Number);
let tmp = [];
let check = Array.from({ length: n }).fill(0);
let cnt = 0;

function solve(l) {
  if (l === m) {
    console.log(tmp.join(' '));
    cnt++;
    return;
  } else {
    for (let i = 0; i < n; i++) {
      if (check[i]) continue;
      check[i] = 1;
      tmp[l] = arr[i];
      solve(l + 1);
      check[i] = 0;
    }
  }
}

function solution() {
  solve(0);
  console.log(cnt);
}

solution();