15649.md

N과 M (1)

문제

https://www.acmicpc.net/problem/15649

정답

다음은 백트래킹을 사용하여 구현해야 하는 문제이다.

let [n, m] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .split(" ")
  .map(Number);

// 수열 상태를 저장할 배열 생성 (최대 길이는 m)
const seq = new Array(m).fill(0);
// 1부터 N까지의 숫자 중 쓰일 수 있는 숫자와 없는 숫자를 체크해주는 배열
const visited = new Array(n).fill(false);

// 모든 수열의 조합을 저장할 문자열
let result = "";

function dfs(k) {
  // k는 현재 수열의 원소 개수를 의미하며 인자가 m과 같아지면 재귀를 종료한다.
  if (k === m) {
    const arr = [];
    for (let i = 0; i < m; i++) arr.push(seq[i]);
    return (result += arr.join(" ") + "\n");
  }
  for (let i = 1; i <= n; i++) {
    if (!visited[i]) {
      seq[k] = i;
      visited[i] = true;
      dfs(k + 1);
      // 재귀 종료 후에는 다시 방문하지 않은 상태로 변경
      // 즉 dfs(3)을 호출할 경우 재귀가 끝나므로 visited[3] = false로 변경 후 dfs(2)를 호출한다.
      visited[i] = false;
    }
  }
}

dfs(0);

console.log(result);