백준/1414/MST/불우이웃돕기

백준/1414/MST/불우이웃돕기

문제 해석

다솜이가 모든 인터넷망을 연결하되, 불우이웃에게 기부할 랜선의 가치가 최대가 되야하는 문제이다.( 즉, 다솜이가 인터넷 망을 가장 적은 비용으로 연결해야하는 문제이다. )

문제 풀이

1. 총 네트워크 망(이하 간선)들의 가중치를 합한다.
2. union_find를 통해 가중치가 최소인 스패닝 트리를 구성한다.( 이 때 합쳐지는 간선들의 가중치를 더해둔다.)
3. 하지만 이 스패닝 트리는 모두 연결되어 있다는 가정를 못하기 때문에 모든 노드에 방문치를 두어 확인하다. ( 서브 그래프를 확인하지 못하므로 기각! )
4. 대표 노드가 자기 자신이 노드가 2개 이상일 경우 연결되지 않았거나 혹은 다른 서브 노드 트리를 가지고 있는 경우일 수 있으므로 모든 노드가 연결 되어 있지 않다고 가정한다.
5. 마지막 모든 노드를 연결한 경우에는 총 가중치에서 현재 스패닝 트리를 이루고 있는 간선들의 합을 빼고
6. 아닐 경우는 -1을 출력한다.

1. 총 네트워크 망(이하 간선)들의 가중치를 합한다.

for (int i = 0;i < N;i++)
{
	cin >> temp;
	for (int j = 0;j < N;j++)
	{
		if (temp[j] >= 'a' && temp[j] <= 'z')
		{
			int _temp = temp[j] - 'a' + 1;
			v.push_back(tie(_temp, i, j));
			_sum += _temp;
		}
		else if (temp[j] >= 'A' && temp[j] <= 'Z')
		{
			int _temp = temp[j] - 'A' + 27;
			v.push_back(tie(_temp, i, j));
			_sum += _temp;
		}
	}
}

2. union_find를 통해 가중치가 최소인 스패닝 트리를 구성한다.( 이 때 합쳐지는 간선들의 가중치를 더해둔다.)

::sort(v.begin(), v.end());

int _count = 0;

for (auto cur : v)
{
	// 연결 도시 a,b 가중치 c
	int a, b, c = 0;
	tie(a, b, c) = cur;
	if (!union_find(b, c))
	{
		_count++;
		_connect_sum += a;
	}

	if (_count == N - 1)
	{
		break;
	}
}

for (int i = 0;i < N;i++)
{
	parent(i);
}

3. 하지만 이 스패닝 트리는 모두 연결되어 있다는 가정를 못하기 때문에 모든 노드에 방문치를 두어 확인하다. ( 서브 그래프를 확인하지 못하므로 기각! )

for (auto cur : v)
{
	// 연결 도시 a,b 가중치 c
	int a, b, c = 0;
	tie(a, b, c) = cur;
	if (!union_find(b, c))
	{
		_count++;
		_connect_sum += a;
           visited[b]++;
           visited[c]++;
	}

	if (_count == N - 1)
	{
		break;
	}
}


for (int i = 0;i < N;i++)
{
	parent(i);
}

3. 대표 노드가 자기 자신이 노드가 2개 이상일 경우 연결되지 않았거나 혹은 다른 서브 노드 트리를 가지고 있는 경우일 수 있으므로 모든 노드가 연결 되어 있지 않다고 가정한다.

for (int i = 0;i < N;i++)
{
	parent(i);
}

int _compare_temp = 0;
for (int i = 0;i < N;i++)
{
	if (p[i] == -1)
		_compare_temp++;
}

if (_compare_temp > 1)
	flag = false;

4. 마지막 모든 노드를 연결한 경우에는 총 가중치에서 현재 스패닝 트리를 이루고 있는 간선들의 합을 빼고

5. 아닐 경우는 -1을 출력한다.

if(flag)
{
	cout << _sum - _connect_sum;
}
else
{
	cout << -1;
}

※이 때 정점이 하나일 경우 즉, 자기자신을 제외하고 간선을 받아기 때문에 정점이 하나 일때는 따로 처리해줘야 한다.

if (N == 1)
{
	cin >> temp;
	if (temp[0] >= 'a' && temp[0] <= 'z')
	{
		int _temp = temp[0] - 'a' + 1;
		_sum += _temp;
	}
	else if (temp[0] >= 'A' && temp[0] <= 'Z')
	{
		int _temp = temp[0] - 'A' + 27;
		_sum += _temp;
	}
}

풀이

첫번째 풀이( N=1 일때, 서브 그래프가 존재할 때 불가능)

#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;

vector<tuple<int, int, int>>v;

int visited[50];
vector<int> p(50, -1);

int parent(int num)
{
	if (p[num] == -1)return num;
	return p[num] = parent(p[num]);
}


bool union_find(int u, int v)
{
	u = parent(u); v = parent(v);
	if (u == v)return true;
	if (u < v)p[v] = u;
	else p[u] = v;
	return false;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// 컴퓨터의 수
	int N = 0;

	cin >> N;

	string temp = "";

	// 가중치 최대 합
	int _sum = 0;
	int _connect_sum = 0;
	bool flag = true;

	for (int i = 0;i < N;i++)
	{
		cin >> temp;
		for (int j = 0;j < N;j++)
		{
			if (temp[j] >= 'a' && temp[j] <= 'z')
			{
				int _temp = temp[j] - 'a' + 1;
				v.push_back(tie(_temp, i, j));
				_sum += _temp;
			}
			else if (temp[j] >= 'A' && temp[j] <= 'Z')
			{
				int _temp = temp[j] - 'A' + 27;
				v.push_back(tie(_temp, i, j));
				_sum += _temp;
			}
		}
	}

	::sort(v.begin(), v.end());

	int _count = 0;

	for (auto cur : v)
	{
		// 연결 도시 a,b 가중치 c
		int a, b, c = 0;
		tie(a, b, c) = cur;
		if (!union_find(b, c))
		{
			_count++;
			_connect_sum += a;
            visited[b]++;
            visited[c]++;
		}

		if (_count == N - 1)
		{
			break;
		}
	}


	for (int i = 0;i < N;i++)
	{
		parent(i);
	}

	int _compare_temp = 0;
	for (int i = 0;i < N;i++)
	{
		if (p[i] == -1)
			_compare_temp++;
	}

	if (_compare_temp > 1)
		flag = false;
	

	if(flag)
	{
		cout << _sum - _connect_sum;
	}
	else
	{
		cout << -1;
	}

	return 0;
}

두번째 풀이

#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;

vector<tuple<int, int, int>>v;
vector<int> p(50, -1);

int parent(int num)
{
	if (p[num] == -1)return num;
	return p[num] = parent(p[num]);
}


bool union_find(int u, int v)
{
	u = parent(u); v = parent(v);
	if (u == v)return true;
	if (u < v)p[v] = u;
	else p[u] = v;
	return false;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// 컴퓨터의 수
	int N = 0;

	cin >> N;

	string temp = "";

	// 가중치 최대 합
	int _sum = 0;
	int _connect_sum = 0;
	bool flag = true;

	if (N == 1)
	{
		cin >> temp;
		if (temp[0] >= 'a' && temp[0] <= 'z')
		{
			int _temp = temp[0] - 'a' + 1;
			_sum += _temp;
		}
		else if (temp[0] >= 'A' && temp[0] <= 'Z')
		{
			int _temp = temp[0] - 'A' + 27;
			_sum += _temp;
		}
	}
	else
	{
		for (int i = 0;i < N;i++)
		{
			cin >> temp;
			for (int j = 0;j < N;j++)
			{
				if (temp[j] >= 'a' && temp[j] <= 'z')
				{
					int _temp = temp[j] - 'a' + 1;
					v.push_back(tie(_temp, i, j));
					_sum += _temp;
				}
				else if (temp[j] >= 'A' && temp[j] <= 'Z')
				{
					int _temp = temp[j] - 'A' + 27;
					v.push_back(tie(_temp, i, j));
					_sum += _temp;
				}
			}
		}

		::sort(v.begin(), v.end());

		int _count = 0;

		for (auto cur : v)
		{
			// 연결 도시 a,b 가중치 c
			int a, b, c = 0;
			tie(a, b, c) = cur;
			if (!union_find(b, c))
			{
				_count++;
				_connect_sum += a;
			}

			if (_count == N - 1)
			{
				break;
			}
		}


		for (int i = 0;i < N;i++)
		{
			parent(i);
		}

		int _compare_temp = 0;
		for (int i = 0;i < N;i++)
		{
			if (p[i] == -1)
				_compare_temp++;
		}

		if (_compare_temp > 1)
			flag = false;
	}

	if(flag)
	{
		cout << _sum - _connect_sum;
	}
	else
	{
		cout << -1;
	}

	return 0;
}