백트래킹


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를 출력한다.