[백준 1414] 불우이웃돕기 (C++)

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

 

문제

---

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

 

출력

---

첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.

 

문제 풀이

---

컴퓨터 모두가 연결되어 있는 형태이면서 랜선의 길이가 최솟값이 되려면 MST를 가져야 한다.

랜선의 길이 오름차순 정렬되는 우선순위 큐를 이용해 랜선의 연결 정보(A 컴퓨터 인덱스, B컴퓨터 인덱스, 랜선의 길이)를 저장한다. 우선순위 큐의 top을 하나씩 꺼내며 두 컴퓨터가 연결되어 있는지 확인한다.

연결되어 있는지 확인하는 방법은 union-find를 사용한다. 두 컴퓨터의 부모 노드를 확인하여 같은 집합에 있는지 확인하고, 아니라면 union()함수를 이용해 연결해준다. 만약 같은 집합에 있다면 연결할 필요가 없다.

MST가 제대로 만들어졌다면 연결된 노드는 N개이고, 연결된 엣지는 N-1개가 된다. 그렇지 않다면 모든 컴퓨터가 연결되어 있는 않은 상태이므로 -1을 출력한다.

 

아래는 코드.

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
int* parents;
int N;

struct info
{
	int start;
	int end;
	int cost;
	info(int a, int b, int c)
	{
		start = a;
		end = b;
		cost = c;
	}
};

struct cmp
{
	bool operator()(info& i1, info& i2)
	{
		if (i1.cost <= i2.cost)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
};

int findParent(int x)
{
	if (parents[x] == x)
	{
		return x;
	}
	else
	{
		return parents[x] = findParent(parents[x]);
	}
}

void merge(int x, int y)
{
	int xParent = findParent(x);
	int yParent = findParent(y);
	if (yParent < xParent)
	{
		parents[xParent] = yParent;
	}
	else
	{
		parents[yParent] = xParent;
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int answer = 0;
	int connectedNode = 1;
	string str;
	cin >> N;
	parents = new int[N];
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 0; i < N; i++)
	{
		parents[i] = i;
	}
	for (int i = 0; i < N; i++)
	{
		cin >> str;
		for (int j = 0; j < str.length(); j++)
		{
			if (str.at(j) != '0')
			{
				int length = 0;
				if (str.at(j) >= 97)
				{
					length = str.at(j) - 96;
				}
				else
				{
					length = str.at(j) - 38;
				}
				pq.push(info(i, j, length));
			}
		}
		
	}
	while (!pq.empty())
	{
		info current = pq.top();
		int startParent = findParent(current.start);
		int endParent = findParent(current.end);
		if (startParent != endParent)
		{
			merge(startParent, endParent);
			connectedNode++;
		}
		else
		{
			answer += current.cost;
		}
		pq.pop();
	}
	if (connectedNode == N)
	{
		cout << answer << "\n";
	}
	else
	{
		cout << -1 << "\n";
	}
	return 0;
}