[백준] 스타트와 링크 - 14889

const N = 4;
const point = [
  [0, 1, 2, 3],
  [4, 0, 5, 6],
  [7, 1, 0, 2],
  [3, 4, 5, 0],
];

const startTeam = [];
let linkTeam = [];
const half = N / 2;

const visited = Array(N).fill(0);

let min = Infinity;

dfs(0);

console.log(min);

function dfs(index) {
  // 종료 조건, 원하는 데이터의 형태가 만들어 졌을 때.
  if (index === half) {
    let sumOfStartTeam = 0;
    let sumOfLinkTeam = 0;

    // 스타트팀에 속하지 않는 사람은 링크팀에 넣는다.
    for (let i = 1; i <= N; i++) {
      if (startTeam.indexOf(i) === -1) {
        linkTeam.push(i);
      }
    }

    
    // 스타트팀과 링크팀의 값을 더한다.
    for (let j = 0; j < half - 1; j++) {
      for (let k = j + 1; k < half; k++) {
        sumOfStartTeam +=
          point[startTeam[j] - 1][startTeam[k] - 1] + point[startTeam[k] - 1][startTeam[j] - 1];
        sumOfLinkTeam +=
          point[linkTeam[j] - 1][linkTeam[k] - 1] + point[linkTeam[k] - 1][linkTeam[j] - 1];
      }
    }

    const diffOfSum = Math.abs(sumOfLinkTeam - sumOfStartTeam);

    if (min > diffOfSum) {
      min = diffOfSum;
    }

    linkTeam = [];
    return;
  }

  // 수열을 만들기 위한 백트래킹
  for (let i = 0; i < N; i++) {
    if (visited[i] === 1)  {
      continue;
    }

    visited[i] = 1;
    startTeam.push(i + 1);
    dfs(index + 1);

    startTeam.pop();
    visited[i] = 0;
  }
}