백준 4386 별자리 만들기 js

4386번: 별자리 만들기

풀이.

별자리들의 좌표가 주어졌을 때 최소 비용으로 모든 별자리를 잇는 최소 스패닝 트리 문제입니다.

union-find개념과 더불어 크루스칼 알고리즘을 공부하면 쉽게 풀 수 있는 문제입니다.

 

union-find의 개념은 여기서 쉽게 배울 수 있습니다.

크루스칼 알고리즘은 여기서 쉽게 배울 수 있습니다.

 

1. 모든 별자리를 입력받고 모든 경우의 별자리 사이의 거리를 queue 변수에 담아줍니다.

2. 비용을 기준하여 오름차순 정렬해줍니다.

3. 무한 루프가 생기지 않도록 union-find를 통해 부모가 같지 않을 경우 두 별자리를 이어줍니다.

    3-1. 동시에 비용을 result 변수에 더해줍니다.

 

정답.

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

let N;
let input = [];

function unionFind(N) {
  this.parents = Array.from({ length: N }, (_, i) => i);

  this.getParent = (num) => {
  	if (num === parents[num]) return num;
    return (parents[num] = this.getParent(num));
  }
  
  this.unionParent = (a, b) => {
  	const aParent = this.getParent(a);
    const bParent = this.getParent(b);
    
    if (aParent > bParent) this.parents[aParent] = bParent;
    else this.parents[bParent] = aParent;
  }
  
  this.find = (a, b) => {
  	const aParent = this.getParent(a);
    const bParent = this.getParent(b);
    
    return aParent === bParent;
  }
}

rl.on("line", function (line) {
  if (!N) {
    N = +line;
  } else {
    input.push(line.split(" ").map((num) => +num));

    if (input.length === N) rl.close();
  }
}).on("close", function () {
  const uf = new unionFind(N);
  let queue = [];

  for (let i = 0; i < N; i++) {
    for (let j = i + 1; j < N; j++) {
      const a = input[i];
      const b = input[j];

      const dist = +Math.sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2).toFixed(
        2
      );
      queue.push([i, j, dist]);
    }
  }

  let result = 0;
  let cnt = 0;
  let index = 0;
  queue.sort((a, b) => a[2] - b[2]);
  while (true) {
    const [a, b, dist] = queue[index++];

    if (!uf.find(a, b)) {
      result += dist;
      uf.unionParent(a, b);
      cnt += 1;
    }
    if (cnt === N - 1) break;
  }

  console.log(result);
  process.exit();
});

 두 별자리 사이의 거리가 비용으로 queue에 담을 때 우선순위 큐를 이용해도 되지만, 노드의 개수가 많지 않아 단순 정렬로도 쉽게 풀리는 문제입니다.