[PS]#Roads and Libraries

 

---

 

https://www.hackerrank.com/challenges/torque-and-development/problem?isFullScreen=true

Roads and Libraries | HackerRank

 

#include <bits/stdc++.h>

using namespace std;

#define PII pair<int, int>

int q, n, m, c_lib, c_road, parent[100001], rrank[100001], cnt[100001];

int Find(int x)
{
	if (parent[x] == x) return x;
	return parent[x] = Find(parent[x]);
}

void Union(int x, int y)
{
	int X = Find(x), Y = Find(y);
	if (X == Y) return;

	if (rrank[X] > rrank[Y]) swap(X, Y);

	parent[X] = Y;
	cnt[Y] += cnt[X] + 1;
	if (rrank[X] == rrank[Y]) ++rrank[Y];
}

long roadsAndLibraries(vector<PII> vec)
{
	if (c_lib <= c_road) return static_cast<long>(n) * static_cast<long>(c_lib);

	for (int i = 0; i < vec.size(); ++i)
	{
		int f = vec[i].first, s = vec[i].second;
		Union(f, s);
	}

	long ret = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (parent[i] != i) continue;
		ret += (long)c_lib;
		ret += static_cast<long>(c_road) * static_cast<long>(cnt[i]);
	}
	return ret;
}

 

* 문제 풀이 과정

 

Disjoint set 알고리즘을 이용함으로써 싸이클 예방과 동시에 구역을 구별할 수 있기에 적절하다.

이를 이용해 문제에서 말하는 최소 건설 비용을 구할 수 있다.

( c_load 길 수리비용, c_lib 도서관 건설 비용 )

n 개의 도시에서 최소 1개의 도서관이 필요하고 길을 수리해서 다른 도시의 도서관을 다닐 수 있다.

모든 노드가 도서관을 갈 수 있게 하는 최소 비용을 구하는 것이 문제의 목적이다.

 

구역 구별은 parent[i] = i 일 때 판별 가능하고 Union 이 실행될 때 붙여지는 구역의 연결된 길의 갯수를 더해준다.

이 때, 합쳐지는 구역의 길의 갯수는 1개가 아닐 수 있다.

최적화를 위해 rank 를 구별해서 구현할 수도 있겠다.

 

또 한가지 조심해야할 것은 결과 값이 int 범위를 초과한다는 점이다.