백트래킹

2023. 05. 29.

15649번 (N과 M (1))

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split(' ');
const N = +input.shift();
const M = +input.shift();

const isVisited = new Array(N);
let output = [];
let result = '';

function dfs(cnt) {
  if (cnt === M) {
    result += `${output.join(' ')}\n`;
    return;
  }

  for (let i = 0; i < N; i++) {
    if (isVisited[i] === true) continue;
    isVisited[i] = true;
    output.push(i + 1);
    dfs(cnt + 1);
    output.pop();
    isVisited[i] = false;
  }
}

dfs(0);
console.log(result.trim());

output에 숫자를 넣어가면서 cnt가 M일 때 result에 이를 삽입한다.

isVisited를 이용해서 output에 담겨있는 숫자를 확인하고 담겨있을 경우 continue로 스킵한다.

output에 해당 숫자를 넣고 재귀로 dfs를 다시 호출한다.

다시 숫자를 제거하고 isVisited도 false로 해준다.

위 코드의 input이 [4, 2]일 때 dfs함수의 최상단에서 각 변수를 디버깅하면 아래와 같다.

15650번 (N과 M (2))

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split(' ');
const N = +input.shift();
const M = +input.shift();

const isVisited = new Array(N);
let output = [];
let result = '';

function dfs(cnt) {
  if (cnt === M) {
    result += `${output.join(' ')}\n`;
    return;
  }

  for (let i = 0; i < N; i++) {
    if (isVisited[i] === true) continue;
    isVisited[i] = true;
    output.push(i + 1);
    dfs(cnt + 1);
    output.pop();
    isVisited[i] = false;
  }
}

dfs(0);

const resultArr = result
  .trim()
  .split('\n')
  .map(el => el.split(' ').map(Number))
  .map(el => el.sort().join(' '));

const answer = [...new Set(resultArr)];

console.log(answer.join('\n'));

여기서는 순열이 아닌 조합을 찾아야 하므로 15649문제에서 가공했다.

중복을 제거하고, 오름차순으로 만들기 위해 각 숫자들을 숫자형으로 바꾸고, sort()한 후 다시 문자열로 합쳤다.

이후 중복을 제거했다.

15651번 (N과 M (3))

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split(' ');
const N = +input.shift();
const M = +input.shift();

let output = [];
let result = '';

function dfs(cnt) {
  if (cnt === M) {
    result += `${output.join(' ')}\n`;
    return;
  }

  for (let i = 0; i < N; i++) {
    output.push(i + 1);
    dfs(cnt + 1);
    output.pop();
  }
}

dfs(0);
console.log(result.trim());

중복이 가능하므로 isVisited 없이 실행했다.

15652번 (N과 M (4))

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split(' ');
const N = +input.shift();
const M = +input.shift();

let output = [];
let result = '';

function isIncreasing(output) {
  let isIncreasing = true;

  for (let i = 0; i < output.length - 1; i++) {
    if (output[i] > output[i + 1]) {
      isIncreasing = false;
    }
  }

  return isIncreasing;
}

function dfs(cnt) {
  if (isIncreasing(output)) {
    if (cnt === M) {
      result += `${output.join(' ')}\n`;
      return;
    }
  } else {
    return;
  }

  for (let i = 0; i < N; i++) {
    output.push(i + 1);
    dfs(cnt + 1);
    output.pop();
  }
}

dfs(0);
console.log(result.trim());

isIncreasing이라는 함수를 만들어 비내림차순인지 확인하고 아닐 경우 return 해주었다.

14889번 (스타트와 링크)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');

const N = +input[0];
const teamNum = N / 2;
const stats = input.slice(1).map(str => str.split(' ').map(Number));

let isVisited = new Array(N);
const start = [];
let link = [];
let min = Infinity;

function dfs(cnt) {
  if (cnt === teamNum) {
    link = [];
    let startSum = 0;
    let linkSum = 0;

    for (let i = 0; i < N; i++) {
      if (!start.includes(i)) {
        link.push(i);
      }
    }

    for (let j = 0; j < teamNum - 1; j++) {
      for (let k = j + 1; k < teamNum; k++) {
        startSum += stats[start[j]][start[k]] + stats[start[k]][start[j]];
        linkSum += stats[link[j]][link[k]] + stats[link[k]][link[j]];
      }
    }

    const diff = Math.abs(startSum - linkSum);
    min = Math.min(diff, min);
    return;
  }

  for (let i = 0; i < N; i++) {
    if (isVisited[i] === true) continue;
    isVisited[i] = true;
    start.push(i);
    dfs(cnt + 1);
    start.pop();
    isVisited[i] = false;
  }
}

dfs(0);

console.log(min);

백트래킹을 이용해 한 팀이 나오는 경우의 수를 모두 구하고, 그 경우에 두 팀의 스탯을 비교한다.

14888번 (연산자 끼워넣기)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const numArr = input[0].split(' ').map(Number);
const operator = input[1].split(' ').map(Number);
let operatorArr = [];

for (let i = 0; i < operator.length; i++) {
  for (let j = 0; j < operator[i]; j++) {
    operatorArr.push(i);
  }
}

let result = 0;
let min = Infinity;
let max = 0;
let isVisited = new Array(N - 1).fill(false);
let output = [];

function calculate(output) {
  let result = numArr[0];
  for (let i = 0; i < N; i++) {
    if (output[i] === 0) {
      result = result + numArr[i + 1];
    } else if (output[i] === 1) {
      result = result - numArr[i + 1];
    } else if (output[i] === 2) {
      result = result * numArr[i + 1];
    } else if (output[i] === 3) {
      if (result < 0) {
        result = Math.abs(result);
        result = -Math.floor(result / numArr[i + 1]);
      } else {
        result = Math.floor(result / numArr[i + 1]);
      }
    }
  }
  return result;
}

function dfs(cnt) {
  if (cnt === N - 1) {
    result = calculate(output);
    if (result < min) {
      min = result;
    }
    if (result > max) {
      max = result;
    }
  }

  for (let i = 0; i < N - 1; i++) {
    if (isVisited[i]) continue;
    isVisited[i] = true;
    output.push(operatorArr[i]);
    dfs(cnt + 1);
    isVisited[i] = false;
    output.pop();
  }
}

dfs(0);

console.log(max + '\n' + min);

dfs를 이용해서 연산자의 조합을 모두 구한다.

해당 연산자의 조합으로 연산을 하고 그 결과들의 min과 max를 출력한다.