[백준_14889] 스타트와 링크 ( 백트래킹 - 자바스크립트 )

문제

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

14889번: 스타트와 링크

 

How to Solve ?

 

이 문제를 풀어 보기 전에 15649 - N과 M(1) 을 풀어본다면 백트래킹을 푸는데 용이 할 것이다.  필자가 푼 문제의 링크를 추후에 공유 해둘테니 DFS, BFS의 맛을 본 학습자라면 이 기회를 통해 "백트래킹"을 학습 해보길 !

 

https://kimbangg.tistory.com/207

[백준_15649] N과 M(1) [ 백트래킹(기초) - 자바스크립트 )

 

 

[1] 백트래킹

 

백트래킹이란, DFS의 특징을 유지하지만 "필요 없다고" 판단되는 길은 가지 않도록 설정한 알고리즘이다.

 

스타트와 링크의 예시를 보면, 4가 주어졌을 때  스타트 팀이 구성 될 수 있는 경우는

 

[1,2] [1,3] ,[1,4] .. [2,1] [2,3] 등 인데, 백트래킹이 아닌 DFS만을 사용 한다면 [1,1] [2,2] 과 같은 중복 값이 나올 수도 있다.

 

1) 그리하여 아래의 코드를 통해서, 수열의 값들을 추가 해주고,

  for (let i = 0; i < N; i++) {
    if (visited[i] === 1) continue;

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

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

 

2) 다음과 같이 설정 해놓은 길이에 맞는 수열이 오면 ( [1,2], [1,3] .. ) 

const half = Math.floor(N/2);

if (index === half) {

}

 

 

3) 주어진 정보를 통해, 팀을 구성 + 점수 차이를 구한다.

 if (index === half) {
    let startSum = 0;
    let linkSum = 0;

    for (let i = 1; i <= N; i++) {
      if (start.indexOf(i) === -1) {
        link.push(i);
      }
    }

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

    let diff = Math.abs(linkSum - startSum);

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

    link = [];
    return;
  }

 

전체 코드

function dfs(index) {
 
  // 원하는 인덱스, 배열의 크기가 됬을 때 etc) [1,2].. 
  if (index === half) {
    let startSum = 0;
    let linkSum = 0;
	
    // 인덱스 값 -1 == 스타트팀 안에 없는 숫자임을 의미.
    for (let i = 1; i <= N; i++) {
      if (start.indexOf(i) === -1) {
        link.push(i);
      }
    }
	
    // 스타트와 링크 팀의 값을 더한다.
    for (let j = 0; j < half - 1; j++) {
      for (let k = j + 1; k < half; k++) {
        startSum +=
          point[start[j] - 1][start[k] - 1] + point[start[k] - 1][start[j] - 1];
        linkSum +=
          point[link[j] - 1][link[k] - 1] + point[link[k] - 1][link[j] - 1];
      }
    }
 
    let diff = Math.abs(linkSum - startSum);

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

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

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

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

// local test
const N = 4;

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

const start = [];
let link = [];
const half = Math.floor(N / 2);

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

let min = Infinity;

dfs(0);
console.log(min);