[백준][크루스칼] 1922 네트워크 연결 NodeJs 구현

목차

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

문제

 

문제 구현 방향

아래 블로그를 참고해서 NodeJs로 구현했다.

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-MST

[그리디] 크루스칼, 프림 알고리즘

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let parent = Array(100001);
for (let i = 0; i < parent.length; i++) {
  parent[i] = i;
}
function findParent(x) {
  if (x === parent[x]) return x;
  return (parent[x] = findParent(parent[x]));
}

function unionParent(a, b) {
  a = findParent(a);
  b = findParent(b);

  if (a < b) parent[b] = a;
  else parent[a] = b;
}

let edge = Array.from({ length: 1000001 }, () => []);

for (let i = 2; i < input.length; i++) {
  let ar = input[i].trim().split(" ").map(Number);
  edge.push([...ar]);
}

edge.sort((a, b) => a[2] - b[2]);
let result = 0;
for (let [a, b, cost] of edge) {
  if (findParent(a) != findParent(b)) {
    unionParent(a, b);
    result += cost;
  }
}
console.log(result);