[백준15649_자바스크립트(javascript)] - N과 M(1)

🔴 문제

N과 M(1)

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, m] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split(' ')
  .map((it) => Number(it));

let answer = '';

const bt = (target, cnt) => {
  if (cnt === m) {
    answer += target + '\n';
    return;
  }
  for (let i = 1; i <= n; i++) {
    if (target.includes(i)) continue;
    bt(target + ' ' + i, cnt + 1);
  }
};

for (let i = 1; i <= n; i++) {
  bt(i.toString(), 1);
}
console.log(answer);

🟢 풀이

백트래킹의 기본 유형
백트래킹이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법으로 쉽게 말해 모든 경우의 수를 따져주다가 더 이상 경우의 수가 없다면 이전단계로 돌아가 다시 모든 경우의 수를 따져주는 유형이다.

위의 문제에서(tc : 4 4)

• 첫번째 숫자 결정 : 첫번째 숫자는 1, 2, 3, 4에서 선택할 수 있다. (1선택)
• 두번째 숫자 결정 : 첫번째 숫자가 1일경우 두번째 숫자는 1을 제외한 2, 3, 4에서 선택할 수 있다. (2선택)
• 세번째 숫자 결정 : 첫번째 숫자가 1이고 두번째 숫자가 2일 경우 세번째 숫자는 1과 2를 제외한 3, 4에서 선택할 수 있다.(3선택)
• 네번째 숫자 결정 : 첫번째 숫자가 1이고 두번째 숫자가 2고 세번째 숫자가 3일 경우 네번째 숫자는 1과 2와 3을 제외한 4 하나만 선택할 수 있다.(4선택)

네번째 숫자가 될수 있는 모든경우의 수를 조회했으니 이전 단계인 세번째 숫자로 돌아가 4를 선택해준다.

이 방식을 반복하면 문제에서 원하는 출력결과를 도출할 수 있다.
1234
1243
1324
...
...

bt 재귀함수의 탈출 조건은 내가 m개의 숫자를 다 골랐는가?이고 bt함수의 두번째 파라미터로 선택한 숫자의 개수를 전달해 탈출조건을 명시해 주었다.

똑같은 숫자를 두 번 고를 수 없으니 아래의 조건문을 사용하여 똑같은 숫자를 고른 경우를 없애주었다.

if (target.includes(i)) continue;

🔵 Ref