네트워크 연결

문제

언어

  • JavaScript

순서도

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

문제 풀이 step 1

  • 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려고 합니다.
  • 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 합니다.
  • 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 합니다.
  • 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것입니다.
  • 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하는 문제입니다.
  • 모든 컴퓨터를 연결할 수 없는 경우는 없다고 합니다.

문제 풀이 step 2

  • 본 문제는 최소 스패닝 트리를 구하는 문제로 크루스칼 알고리즘을 적용하면 쉽게 구할 수 있습니다.
  • 우선, 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 (this.parent[u] === 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 n = Number(input[0]);
	const m = Number(input[1]);

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

	let cost = 0;
	const dj = new DisjointSet(n + 1);

	// 가중치가 작은 간선부터 사이클이 생기지 않는다면 추가
	for (let i = 0; i < m; i++) {
		const [f, t, c] = edges[i];

		if (dj.find(f) === dj.find(t)) continue;

		dj.union(f, t);
		cost += c;
	}

	return cost;
};

console.log(solution(input));