백준 15649번: N과 M (1) - javascript

백준 15649번: N과 M (1)

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

접근

처음에는 무작정 재귀로 짜보려다가 max call 에러가 나버려서 검색을 해보니 백트래킹 계열의 문제란다.
백트래킹이 무었이냐? 약간 우리식으로 번역하면 ‘한 수 만 물러줘’ 같은 것일까..
백트래킹은 모든 방법을 탐색하는 brute force 알고리즘에서 주로 사용된다.
완전 탐색의 방법으로는 bfs나 dfs가 있는데 백트래킹은 주로 dfs에서 효율적이다.
dfs는 갈 수 있는 최대 깊이까지 갔다가 돌아오는 탐색방법인데, 우리는 끝까지 탐색하지 않아도 중간에 조건에 부합하지 않는 경우가 있어서 현재 경로가 잘 못 된 것 임을 알 수 있는 경우가 종종 있다.

이런 알면서도 들어가는 비효율적인 경우를 가지치기 하기 위해 백트래킹이 사용된다고 한다.
간단하게 말하면 DFS에 조건을 걸어놓고 조건에 부합하지 않으면 해당 가지는 거기서 더 이상 들어가지 않는 것이다.

다시 문제로 돌아와서, 이번 문제는 주어진 수 N까지의 자연수들로 M의 길이를 충족하는 중복되지 않는 수열을 만드는 것이다.
즉 123, 132 같은것은 되지만 113같은 중복수열은 안된다는 뜻이다.

일단은, 주어진 범위가 1부터 8까지여서 간단했다. 0에서 8까지 false값을 갖는 check배열을 두어 현재 수열이 갖고있는 숫자들의 정보를 가진 배열을 만들고 dfs의 형식으로 끝까지 내려간다.
이때 check 배열을 이용해서 지금 주어진 숫자를 수열에 넣어도 되는지 체크하고, 넣어도 되면 주어진 깊이까지 마저 내려가고, 아니면 지나친다.

최종적인 깊이까지 내려오면 또 다른 전역변수 result에 지금까지 만들어온 길이 M의 수열을 넣어준다.
이 과정을 반복문을 통해 돌려주면 당연히 결과로 나온 수열은 사전 순으로 증가하는 순서대로 출력하게 된다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let list = [];
let result = [];
let check = new Array(9).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer =0;
  input = input[0].split(' ');
  let n = input[0];
  let m = input[1];
  re(0,n,m);
  console.log(result.join('\n'));
  process.exit();
});

let re = function(cnt,n,m){
  if(cnt==m){
    result.push(list.join(' '))
    return 1;
  }
  for(let i=1;i<=n;i++){
    if(!check[i]){
      check[i] = true;
      list[cnt] = i;
      re(cnt+1,n,m);
      check[i] = false;
    }
  }
  return 1;
}