도시 분할 계획

문제

언어

  • JavaScript

순서도

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

문제 풀이 step 1

  • 마을은 N 개의 집과 그 집들을 연결하는 M 개의 길로 이루어져 있습니다.
  • 길은 어느 방향으로든지 다닐 수 있는 편리한 길입니다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있습니다.
  • 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있습니다.
  • 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 합니다.
    • 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻입니다.
    • 마을에는 집이 하나 이상 있어야 합니다.
  • 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었습니다.
  • 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있습니다.
  • 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있습니다.
  • 마을의 이장은 위 조건을 만족하다록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶습니다.
  • 이것을 구하는 문제입니다.

문제 풀이 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, m] = input[0].split(" ").map(Number);
	const edges = input
		.slice(1)
		.map((v) => v.split(" ").map(Number))
		.sort((a, b) => a[2] - b[2]);

	const dj = new DisjointSet(n + 1);

	// 크루스칼 알고리즘 적용
	let cnt = 0;
	const costs = [];
	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);
		costs.push(c);
		cnt += c;
	}

	// 그래프에 포함되는 간선들 중에서 가장 가중치가 큰 간선 제거
	return cnt - costs[n - 2];
};

console.log(solution(input));