[백준] node.js/ 15649 N과 M 1

내 풀이

const fs = require('fs');

let [n, m] = (fs.readFileSync('./dev/stdin') + '').toString().trim().split(' ');

let ans = [];
let visit = new Array(parseInt(n)).fill(false);

const back = (d, n, m) => {

  // m개의 원소까지 찼는지 확인
  if (d === m) {
    console.log(...ans);
    return;
  }
  
  for (let i = 0; i < n; i++) {
    if (!visit[i]) {
      visit[i] = true;
      ans.push(i + 1);

      back(d + 1, n, m);

      ans.pop();
      visit[i] = false;
    }
  }
};

back(0, parseInt(n), parseInt(m));

사실 이번 문제는 백트래킹 문제인것이 파악되서 기존에 풀었던 🔗 파이썬 풀이를 참고하여 풀이했다.

 

n개의 원소를 가진 visit이라는 boolean flag를 만들어

각 요소의 내부로  돌 때 본인의 값을 가져오지 않도록 했다.

 

 

 

 

 

예시 살펴보기

 

실제 console 을 찍어 자세히 살펴보면 가장 바깥 수를 방문 완료로 걸어두고

그 내부에서 ans가 m개가 될때까지 계속 돌게 된다.

d === m 이되면 다 찬 ans의 값을 출력한 후 , return 해서 나오고

이전에 돌던 for문으로 돌아가 마저 돌게 된다.

 

4,2  입력 시 

const fs = require('fs');

let [n, m] = (fs.readFileSync('./dev/stdin') + '').toString().trim().split(' ');

let ans = [];
let visit = new Array(parseInt(n)).fill(false);

const back = (d, n, m) => {
  console.log(d, n, m, '****************');
  if (d === m) {
    console.log(...ans);
    returnl
  }
  for (let i = 0; i < n; i++) {
    console.log('i:', i, 'visit:', visit, 'ans:', ans);
    if (!visit[i]) {
      visit[i] = true;
      ans.push(i + 1);

      back(d + 1, n, m);

      ans.pop();
      visit[i] = false;
    }
  }
};

back(0, parseInt(n), parseInt(m));