백준 node.js 1197번 최소 스패닝 트리, 최소 신장 트리 크루스칼 JavaScript JS

1197번: 최소 스패닝 트리

😉문제 설명

이 문제는 이름 그대로 최소 신장 트리 문제입니다.

최소 신장 트리는 모든 노드를 최소한의 가중치로 모든 간선을 연결 한 것을 말합니다.

문제를 풀기위해서 크루스칼 알고리즘을 사용합니다!

---

😎문제 풀이

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

const [V, E] = input.shift().split(" ").map(Number)
const lines = [];
for(let data of input){
  const [node1, node2, cost] = data.split(" ").map(Number)
  lines.push({node1,node2,cost})
}

function find(parent, x){
  if(parent[x] === x){
    return x
  }
  //경로 압축
  return parent[x] = find(parent,parent[x])
}

function union(parent, a, b){
  const pa = find(parent,a)
  const pb = find(parent, b)
  if(pa < pb){
    parent[pb] = pa
  }else{
    parent[pa] = pb
  }
}

lines.sort((a,b)=>a.cost - b.cost)
const parent = Array.from({length:V+1},(_,i)=>i)
let answer = 0;
for(let {node1,node2,cost} of lines){
  if(find(parent,node1) !== find(parent,node2)){
    union(parent, node1, node2)
    answer += cost
  }
}

console.log(answer)