Node.js) 백준 1647번: 도시 분할 계획

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

1647번: 도시 분할 계획

 

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));

const [N, K] = input.shift();

class Edge {
	constructor(src, dest, cost = 0) {
		this.src = src;
		this.dest = dest;
		this.cost = cost;
	}
}

class Kruskal {
	//input: [[src,dest,cost], ...]
	constructor(V, input) {
		this.mstCost = 0;
		this.mstNode = new Set();
		this.parent = Array(V)
			.fill(0)
			.map((_, i) => i);
		this.edges = [];

		input.forEach(([s, d, c]) => {
			this.edges.push(new Edge(s, d, c));
		});

		this.edges = this.edges.sort((a, b) => a.cost - b.cost);
	}

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

	union(x, y) {
		if (x < y) this.parent[y] = x;
		else this.parent[x] = y;
	}

	isCycle() {
		for (let i = 0; i < this.edges.length; i++) {
			const x = this.find(this.edges[i].src);
			const y = this.find(this.edges[i].dest);

			if (x == y) {
				return true;
			}

			this.union(x, y);
		}
		return false;
	}

	getMst() {
		for (let i = 0; i < this.edges.length; i++) {
			const { src, dest, cost } = this.edges[i];

			const x = this.find(src);
			const y = this.find(dest);
			if (x != y) {
				this.union(x, y);
				console.log(x, y, cost);
				this.mstCost += cost;
				this.mstNode.add(x);
				this.mstNode.add(y);
			}
		}
	}
}

class KruskalCity extends Kruskal {
	constructor(V, edges) {
		super(V, edges);
		this.maxCostRoute = 0;
	}

	getMst() {
		for (let i = 0; i < this.edges.length; i++) {
			const { src, dest, cost } = this.edges[i];

			const x = this.find(src);
			const y = this.find(dest);
			if (x != y) {
				this.union(x, y);
				this.mstCost += cost;
				if (this.maxCostRoute < cost) this.maxCostRoute = cost;
				this.mstNode.add(x);
				this.mstNode.add(y);
			}
		}
	}
}

const k = new KruskalCity(N + 1, input);
k.getMst();
console.log(k.mstCost - k.maxCostRoute);