별자리 만들기

문제 설명

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

문제 풀이

1. 각 별에서 다른 별까지의 간선을 모두 구한다.
2. 구한 모든 간선들을 정렬한다.(오름차순).
3. 정렬된 간선들로 크루스칼 알고리즘을 사용.(union-find).

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

const getDistance = (startLocation, endLocation) => {
  const [startX, startY] = startLocation;
  const [endX, endY] = endLocation;
  return Math.sqrt(Math.pow(startY - endY, 2) + Math.pow(startX - endX, 2));
};
const float = parseFloat;

const starCount = +input[0];
const visited = Array.from(Array(starCount), (v, i) => i);
const checked = Array(starCount).fill(false);
const star = {};
input.slice(1).forEach((startLocation, idx) => {
  const [x, y] = startLocation.split(" ");
  star[idx] = [float(x), float(y)];
});

const find = star => {
  if (visited[star] === star) return star;
  return find(visited[star]);
};

const edge = [];

const findEdge = start => {
  checked[start] = true;
  for (const key in star) {
    if (key === start) continue;
    if (checked[key]) continue;
    const cost = getDistance(star[start], star[key]);
    edge.push([start, key, cost]);
  }
};

for (const key in star) {
  findEdge(key);
}
edge.sort((a, b) => a[2] - b[2]);

let answer = 0;

for (let i = 0; i < edge.length; i++) {
  const [start, end, cost] = edge[i];
  if (find(start) === find(end)) continue;
  visited[find(end)] = find(start);
  answer += cost;
}

console.log(answer);