[백준1197_자바스크립트(javascript)] - 최소 스패닝 트리

🔴 문제

최소 스패닝 트리

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[v, e], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const edges = inputs.sort((a, b) => a[2] - b[2]);
const p = Array.from({ length: v + 1 }, (_, idx) => idx);

const find = (a) => {
  if (a !== p[a]) p[a] = find(p[a]);

  return p[a];
};

const union = (a, b) => {
  const pa = find(a);
  const pb = find(b);

  p[pb] = pa;
};

let ans = 0;
for (const [s, e, c] of edges) {
  const ps = find(s);
  const pe = find(e);

  if (ps === pe) continue;
  union(s, e);
  ans += c;
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

최소 스패닝 트리란 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중 그 가중치의 합이 최소인 트리를 말한다.

최소 스패닝 트리(MST)를 구하는 방법은 여러가지가 있는데, 그 중에서 제일 많이 사용되는 크루스칼 알고리즘으로 문제를 풀이했다.

크루스칼 알고리즘은 그리디 알고리즘으로 가중치가 제일 작은 간선들부터 이어 트리를 완성시키는 방법이다.

이 때, 모든 간선의 끝까지 탐색하지 않았는데 싸이클이 발생한다면 이는 트리가 아닌 그래프가 되므로 해당 간선은 제거하고, 싸이클이 발생하지 않는 간선만 이어 트리를 완성시키면 된다.

싸이클 발생여부는 유니온파인드를 사용해 확인한다.

이제 코드를 분석해보자!
먼저 파인드, 유니온, 부모배열 p을 정의해주고 간선 정보를 가중치가 낮은 기준으로 정렬해서 edges 배열에 담아줬다.

이제 for문을 통해 모든 간선을 탐색한다.
시작 노드와 끝 노드의 부모값을 구한 뒤, 이 두 값이 같으면 싸이클이 형성된 것으로 continue를 통해 해당 간선은 건너뛴다.

두 값이 다르면 해당 간선을 트리의 일부로 채택해주기 위해 시작노드와 끝 노드를 union연산 해준뒤 그 가중치 값을 ans에 저장해주면 된다.

🔵 Ref

Minimum Spanning Tree (최소신장트리)