백준 14889 < 스타트와 링크 > JavaScript

📍문제 링크

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

14889번: 스타트와 링크

 

📍알고리즘 분류

- 브루트포스

- 백트래킹

 

📍문제 풀이

4 이상의 양수 N과 2차원 배열이 주어질 때,

1 ~ N 까지 숫자들을 절반으로 나누는 가짓수를 구하고 각각 비교한다

 

비교 방법)

집합에서 nP2 (순열) 을 구해서 그 좌표를 2차원 배열의 좌표값으로 사용해 모두 더한 것의 최소값을 비교하여 가장 최소값을 출력

 

1 ~ N 까지 숫자들을 절반으로 나누기 : 백트래킹 이용하여 배열 구하기

백트래킹으로 구한 집합에 대해서 반대의 경우를 filter 함수로 구해준다

(이 부분에서 filter로 나눈 반대의 경우를 계산 완료 처리하면 시간을 절반으로 줄일 수 있다)

 

배열을 구했으면 nP2 순열을 구해서(중첩 for문 이용) 총합을 구한다 (calcScore 함수 이용)

반대의 경우와 절댓값을 구하고 최솟값과 비교하여 업데이트한다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
const calcScore = (map, team) => {
  let score = 0;
  for (let i = 0; i < team.length; i++) {
    for (let j = 0; j < team.length; j++) {
      if (j !== i) score += map[team[i] - 1][team[j] - 1];
    }
  }
  return score;
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const N = +input.shift();
  const players = Array.from({ length: N }, (_, i) => i + 1);
  const board = input.map((row) => row.split(" ").map(Number));
  const chosen = [];
  const isUsed = [];
  let min = Number.MAX_SAFE_INTEGER;

  const recursive = (depth) => {
    if (depth === N / 2) {
      const notChosen = players.filter((el) => !chosen.includes(el));
      min = Math.min(
        min,
        Math.abs(calcScore(board, chosen) - calcScore(board, notChosen)),
      );
      return;
    }

    for (let i = 1; i <= N; i++) {
      if (!isUsed[i]) {
        if (depth >= 1 && chosen[depth - 1] > i) continue;
        chosen[depth] = i;
        isUsed[i] = true;
        recursive(depth + 1);
        isUsed[i] = false;
      }
    }
  };

  recursive(0);
  console.log(min);
});

 

📍리뷰

- 시간복잡도를 줄일 수 있는 방법이 있어 보인다

캐시하는 방법을 구하면 더 좋을텐데