백준 14889 스타트와 링크

문제

해당 문제는 팀들이 가질 수 있는 모든 조합의 수를 구한 다음에 여기서 팀끼리 가지는 차이의 절댓값이 가장 작은 수를 출력하도록 하는 문제이다. 해당 문제는 짝수로 팀이 이루어지기 때문에 N을 반으로 나누고, 또 그 N/2를 다시 2로 나눈 값이 뽑는 두명 짝의 수이다. 이렇게 두명 짝을 미리 맺어놔야 가질 수 있는 능력치가 더해질 수 있다.

그렇기 때문에 먼저 2명씩 짝지어놓고 이렇게 짝지어서 나온 능력치만을 미리 뽑고, 2/N씩 팀으로 나눈 경우의 수를 모두 구하면서 절댓값의 최솟값을 구하면 될 것 같았다. 따라서 모든 경우의 수를 구해야 하는게 핵심이기 때문에 브루트포스로 백트래킹 하면서 구하기로 생각했다

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const N = +n;
const abilityMap = rest.map((r) => r.split(" ").map(Number));
const pairs = [];
const visited = new Array(N).fill(false);
for (let i = 0; i < N; i++) {
  for (let j = i + 1; j < N; j++) {
    pairs.push(abilityMap[i][j] + abilityMap[j][i]);
  }
}
 
let min = Infinity;
function backTrack(start, link, acc) {
  if (!start && !link) {
    min = Math.min(min, Math.abs(acc));
  }
  if (start) {
    for (let i = 0; i < N; i++) {
      if (!visited[i]) {
        visited[i] = true;
        backTrack(start - 1, link, acc + pairs[i]);
        visited[i] = false;
      }
    }
  }
  if (link) {
    for (let i = 0; i < N; i++) {
      if (!visited[i]) {
        visited[i] = true;
        backTrack(start, link - 1, acc - pairs[i]);
        visited[i] = false;
      }
    }
  }
}
backTrack(N / 2, N / 2, 0);
console.log(min);
 

처음에는 이런 식으로 백트래킹을 진행하려고 했다. 스타트와 링크 팀을 각각 백트래킹으로 돌리고, 여기서 누적값을 스타트팀은 더하는 식으로, 링크 팀은 빼는 식으로 백트래킹을 진행하려고 했지만 생각해보니 이렇게 미리 2명씩 짝지어놓으면 나중에 3명이 됐을 때는 기존에 있는 애들과의 능력치도 더해야 하는데 더하지 못하는 상황이 되어버린다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const N = +n;
const abilityMap = rest.map((r) => r.split(" ").map(Number));
const pairs = Array.from({ length: N }, () => Array(N).fill(0));
const visited = new Array(N).fill(false);
 
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    pairs[i][j] = abilityMap[i][j] + abilityMap[j][i];
  }
}
 
let min = Infinity;
 
function backTrack(count, idx) {
  if (count === N / 2) {
    let start = 0,
      link = 0;
 
    for (let i = 0; i < N; i++) {
      for (let j = i + 1; j < N; j++) {
        if (visited[i] && visited[j]) start += pairs[i][j];
        else if (!visited[i] && !visited[j]) link += pairs[i][j];
      }
    }
 
    min = Math.min(min, Math.abs(start - link));
    return;
  }
 
  for (let i = idx; i < N; i++) {
    if (!visited[i]) {
      visited[i] = true;
      backTrack(count + 1, i + 1);
      visited[i] = false;
    }
  }
}
 
backTrack(0, 0);
console.log(min);
 

그래서 요렇게 백트래킹을 하되, 뽑은 사람과 뽑지 않은 사람을 구분하는 방식으로 해서 백트래킹을 진행하다가 N/2가 되면 총 점수를 루프 돌면서 계산해주면 된다. 뽑지 않은 사람을 !visited로 구분할 수 있는 이유는 어차피 2차원 배열에서 가질 수 있는 사람의 수가 딱 반반으로 정해져 있기 때문에 1차원 배열로도 충분히 구별할 수 있었다.