최소 스패닝 트리

문제

언어

  • JavaScript

순서도

  1. DisjointSet 자료구조 구현
  2. 간선들을 가중치를 기준으로 오름차순 정렬
  3. 가중치가 작은 간선들부터 사이클이 생기지 않도록 연결

문제 풀이 step 1

  • 크루스칼 알고리즘을 적용하면 최소 스패닝 트리를 손쉽게 구할 수 있습니다.
  • 우선, DisjointSet 자료구조를 구현합니다.
  • 그리고 주어진 간선들을 가중치를 기준으로 오름차순으로 정렬합니다.
  • 그리고 가중치가 작은 간선부터 DisjointSet 자료구조를 이용해서 사이클이 생기는지 검사하고, 사이클이 생기지 않는다면 그 간선을 포함시킵니다.
  • 포함시킨 간선들의 가중치를 모두 더해서 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

// DisjointSet 자료구조 구현
class DisjointSet {
	constructor(n) {
		this.parent = Array.from(Array(n), (v, i) => i);
	}

	find(u) {
		if (u === this.parent[u]) return u;
		return (this.parent[u] = this.find(this.parent[u]));
	}

	union(u, v) {
		u = this.find(u);
		v = this.find(v);

		if (u === v) return;

		if (u < v) this.parent[v] = u;
		else this.parent[u] = v;
	}
}

const solution = (input) => {
	const [v, e] = input[0].split(" ").map(Number);

	// DisJointSet 초기화
	const ds = new DisjointSet(v + 1);

	// 간선들을 가중치 기준으로 오름차순 정렬
	const edges = input
		.slice(1)
		.map((v) => v.split(" ").map(Number))
		.sort((a, b) => a[2] - b[2]);

	let ans = 0;
	for (let i = 0; i < e; i++) {
		const [f, t, c] = edges[i];

		// 사이클이 생긴다면 포함하지 않음
		if (ds.find(f) === ds.find(t)) continue;

		// 간선을 포함하고, 가중치를 계산
		ds.union(f, t);
		ans += c;
	}

	return ans;
};

console.log(solution(input));