백준_15649: N과 M (1) (node.js/JavaScript)

➡️ 문제: N과 M (1)

 

🧉 제출

let [N, M] = require('fs').readFileSync(0).toString().trim().split(' ');
let arr = [];

function dfs() {
  if (arr.length == M) {
    console.log(arr.join(' '));
    return;
  }
  
  for (let i = 1; i <= N; i++) {
    if (!arr.includes(i)) {
      arr.push(i);
      dfs();
      arr.pop();
    }
  }
}

dfs();

 

🏔️ 과정

 

일단 백트래킹이 뭔가 해서 찾아보니 재귀적으로 풀다가 조건에 맞지 않으면 가지치기(이게 백트래킹)해서 이전으로 돌아가고, 또 다시 재귀적으로 푸는 것을 반복하는 것으로 보였다.

 

그래서 함수를 하나 만들고, 그 안에서 한 줄씩 도출해주는 반복문과 반복문의 종료조건을 설정했다. 순서는 다음과 같다.

 

먼저 반복문에서는 1, 2, .. N까지 순서대로 하나씩 arr에 있는지 체크하고 (중복 체크) 빈배열 arr에 넣는 것을 재귀로 반복함으로서 M개의 요소를 가진 배열로 만들어준다.

그리고 종료조건은 N,M이 주어질 때 한줄에 M개씩 줄바꿈 되어야하니까 arr.length==M이 되면 console로 찍어준다.

그리고 재귀가 끝나면 pop으로 arr을 빈배열로 만들어서 첫번째 요소부터 다음 i로 시작할 수 있게 한다.